ВсОШ-1999, Региональный этап, 10.7
В.Л. Дольников

#2. Каждый голосующий на выборах вносит в избирательный бюллетень фамилии n кандидатов. На избирательном участке находится n+1 урна. После выборов выяснилось, что в каждой урне лежит по крайней мере один бюллетень и при всяком выборе (n+1) -го бюллетеня по одному из каждой урны найдется кандидат, фамилия которого встречается в каждом из выбранных бюллетеней. Докажите, что по крайней мере в одной урне все бюллетени содержат фамилию одного и того же кандидата.

Каналу срочно требуется аватарка

UPD. И это не конкурс идиотских картинок

Клеточки и разрезания по пятницам.

Задача с командной олимпиады проходящего сейчас 61-го Уральского турнира. Задача предлагалась в 8-ом классе под номером 8.

#3. Ацтекский диамант ранга n — это клетчатая фигура «ромбик» из 2n(n + 1) клеток, вдоль каждой «стороны» которого расположено n клеток. При каких n ацтекский диамант ранга n можно разрезать на прямые тетрамино и S-тетрамино (фигурки можно поворачивать и переворачивать)?

#клеточки #разрезания

Вынесу из комментариев решение, которое написал Саша Полянский. Действительно, Владимир Леонидович большой специалист по комбинаторной геометрии, наверняка, его решение имело геометрические мотивы.

Решение задачи #1

Кажется, автор задачи Вл.Л. Дольников и поэтому вряд ли он предлагал решение этой задачи из соображений, предложенное выше (где делится на две части самый тяжелый кусочек сыра). Скорее, его изначальное решение следующее. Представим наши кусочки сыра как однородные отрезки (что тоже предлагалось выше) и сомкнём окружность из них. Любая прямая, проходящая через центр будет делить общую массу пополам. Рассмотрим ориентированную прямую и функция число кусочков справа минус число кусочков слева, тогда из соображений непрерывности (aka Борсук-Улам) - непрерывного вращения прямой - несложно завершается решение. (Еще нужно заметить, что функция принимает четные значения тогда и только, когда прямая проходит через точку стыка и внутренность какого-то отрезка.)

Задача с первого тура проходящего сейчас 61-го Уральского турнира. Задача предлагалась в высшей старшей лиге.

#4. Дан набор из 2n натуральных чисел, сумма которых кратна n. Разрешается выбрать n чисел и прибавить ко всем одно и то же натуральное число. Докажите, что можно сделать все числа равными, выполнив не более 2n − 1 таких операций.

#комбичисла

Задача #2 частенько ставит в ступор, хотя она и не очень сложная.

Предположим противное, то есть в каждой урне для каждого кандидата есть бюллетень, который его не содержит. Перенумеруем урны числами от 1 до n+1. Возьмем произвольный бюллетень из последней урны. В нем n фамилий — занумеруем их числами от 1 до n. Далее возьмем из k-ой урны тот бюллетень, который не содержит k-ую фамилию. Полученный таким образом набор бюллетеней противоречит условию задач.

Граф по понедельникам

Автор А.В. Шаповалов, задача с какого-то Матпраздника.

#5. Среди 49 школьников каждый знаком не менее чем с 25 другими. Докажите, что можно их разбить на группы из двух или трёх человек так, чтобы каждый был знаком со всеми в своей группе.

#граф

Решение задачи #3 с командной олимпиады Уральского турнира.

Решение выглядит довольно традиционна для таких задач — раскраска. Покрасим часть клеток диаманта, как показано на картинке слева (парами диагоналей). Тогда каждое положение одной из предложенных тетраминошек устроено так, что разность числа закрашенных и незакрашенных клеток в ней делится на 4. Но тогда и во всем диаманте число закрашенных клеток должно иметь тот же остаток от деления на 4, что и число незакрашенных. Нетрудно проверить, что это выполнено при n, имеющих остаток 0 или 3 от деления на 4. Разрезания диамантов ранга 3 и 4 приведены на рисунке справа (снизу вверх), там же можно увидеть как делать переход от 4k к 4k+3 и от 4k+3 к 4k+4.

James Propp написал в сентябрьском Math Horizons решение задачи выше

ВсОШ-1999, Регион, 11.3, С.Л. Берлов

#6. В классе каждый болтун дружит хотя бы с одним молчуном. При этом болтун молчит, если в кабинете находится нечетное число его друзей – молчунов. Докажите, что учитель может пригласить на факультатив не менее половины класса так, чтобы все болтуны молчали.

Граф по понедельникам

Решение задачи #5


Мне очень нравится официальное решение этой задачи... Почему Фёдор?

Представим, что сначала все 49 школьников стоят в коридоре, и будем постепенно запускать их в класс. При этом будем делать это так, чтобы в классе в любой момент времени дети были разбиты на требуемые группы. Пусть в коридоре стоит школьник Фёдор. Если он знаком с каким-то другим школьником, стоящим в коридоре, то просто запустим их двоих в класс. Иначе все знакомые Фёдора уже в классе. Так как в классе менее 50 школьников, они разбиты менее чем на 25 групп. Значит, среди знакомых Фёдора какие-то двое находятся в одной группе. Если это группа из двух школьников, то впустим Фёдора в класс, добавив его к этой группе. Если же это группа из трёх школьников, то попросим одного из знакомых Фёдора образовать с ним группу, а оставшихся школьников оставим вдвоём.

Так, постепенно впуская школьников в класс, мы добьёмся того, что все школьники будут разделены на требуемые группы.

Клеточки и разрезания по пятницам.

#7. Можно ли разрезать квадрат на 15 равных шестиугольников?

#разрезания

Разбираем задачу #6 про молчунов и болтунов

Официальное решение задачи состоит в построении искомого набора по индукции. Однако можно поступить иначе.

Пусть у нас k молчунов. Для любого подмножества молчунов (таких 2^k) выберем всех болтунов, которых можно к ним добавить — назовем это подходящей группой. Посчитаем сколько в среднем участников в такой подходящей группе. Каждый молчун попадает ровно в половину таких групп (его можно взять или не взять). Каждый болтун (скажем, Петя) тоже входит ровно в половину таких групп. Действительно, можно выделить петиного молчаливого друга (скажем, Васю) и разбить все подмножества молчунов на пары: содержащие Васю и не содержащие. В каждой паре к одному подмножеству Петю добавить можно, а ко второму нельзя. Поскольку каждый ученик входит ровно в половину подходящих групп, то в какой-то группе не менее половины всех учеников класса.

Граф по понедельникам

61-й Уральский турнир Юных математиков. Второй тур, высшая старшая лига. (Romanian TST 2 2008, Problem 4)

#8. В связном графе с n вершинами каждое ребро содержится хотя бы в одном треугольнике. Найдите наименьшее возможное количество рёбер в этом графе.

#граф

Не знаю, почему на задачу #7 была такая реакция. Мне эта задача кажется довольно прикольной, потому что опирается на факт, который появляется обычно в младшеклассных кружках.

Дело в том, что прямоугольник 5×9 можно разрезать на уголки из трех клеток. А для того, чтобы произвести разрезание квадрата на равные шестиугольники можно взять указанное разрезание прямоугольника 5×9 и растянуть его по вертикали в 9/5 раза.

Комби числа с Венгерской олимпиады 1952-го года

#9. Из целых чисел от 1 до 3n выбрали n+2 каких-то чисел. Доказать, что при n>1 среди выбранных чисел непременно найдутся два таких, разность между которыми больше n, но меньше 2n.

При n = 60 авторы предлагают следующую переформулировку.

Библиотека открывается в 12 часов дня и закрывается в 15 часов. Входит в библиотеку разрешается с интервалом в одну минуту. Первый читатель может войти в библиотеку ровно в 12:00, последний — в 14:59. Входить в библиотеку читателям разрешается только по одному. Через час после прихода в библиотеку читатель засыпает над книгами и спит ровно час, если только закрытие библиотеки не прервет его сон. Входить в библиотеку, когда кто-нибудь из читателей спит, воспрещается. Доказать, что при столь странных правилах 62 человека не смогут побывать в библиотеке за один день.

#комбичисла