Комбинаторика на ММО: графы, турниры, логика, конструктивы

Пусть на симпозиуме лжецов и правдолюбов. По условию

Посмотрим на какого-нибудь лжеца и какого-нибудь правдолюба. Если они знакомы, то правдолюб скажет да, а если незнакомы, то лжец скажет да В любом случае будет ровно один ответ да для каждой такой пары, а всего пар

Минимальное значение этого выражения равно и достигается при или Таким образом, в любом случае будет не менее ответов да

Пример, когда это значение достигается: 99 лжецов и 1 правдолюб, и все друг с другом знакомы.

Решим задачу для прямоугольника , где — произвольные натуральные числа. Мы докажем, что ответом является число

Сначала покажем, что Петя может раскрасить доску так, чтобы при любом разрезании Васи получилось не менее, чем разноцветных доминошек. Покрасим прямоугольник шахматным образом в синий и красный цвета так, чтобы левая нижняя клетка была красной. Пете достаточно добиться того, чтобы в чёрном многоугольнике было на больше синих клеток, чем красных. Действительно, тогда при любом разрезании на доминошки будет хотя бы доминошек, в которых есть синяя клетка чёрного многоугольника, но нет красной (так как в каждой доминошке ровно одна синяя и ровно одна красная клетка), все такие доминошки будут чёрно-белыми.

Занумеруем строки снизу-вверх, а столбцы слева-направо. Добиться такого перевеса синих клеток в чёрном многоугольнике Петя может, например, покрасив в точности следующие клетки в чёрный цвет: все клетки первого столбца, в остальных столбцах с номерами дающими остаток от деления на — все клетки, кроме самой верхней, во всех столбцах с чётными номерами, кроме самого правого, — все синие клетки, во всех остальных столбцах — только самую нижнюю клетку (см рисунок). Действительно, тогда в первом столбце синих и красных клеток одинаковое количество, в остальных столбцах с нечётными номерами красных клеток на одну больше, чем синих, а в каждом чётном столбце, кроме последнего, синих клеток на больше, чем красных, в последнем столбце синих на одну больше, чем красных, итого суммарно синих больше, чем красных, на клеток. При такой покраске как чёрные, так и белые клетки образуют многоугольник.

Теперь докажем, что как бы Петя ни раскрасил клетки, Вася сможет добиться того, чтобы разноцветных доминошек было не более, чем Назовём каёмкой множество всех клеток прямоугольника, прилегающих к границе. Достаточно доказать, что Вася всегда сможет разбить все клетки, отличные от клеток каёмки, на доминошки так, чтобы среди них было не более разноцветных, и что он всегда сможет разрезать каёмку на доминошки так, чтобы среди них было не более одной разноцветной.

Теперь докажем второе утверждение. Для этого достаточно доказать, что белые клетки каёмки образуют связное по сторонам множество клеток. Действительно, тогда в каёмке белые клетки представляют собой несколько последовательных клеток, и Вася может порезать всю каёмку на доминошки, порезав при этом всю белую часть на доминошки, за исключением, возможно, одной клетки (если в каёмке белых клеток нечётное количество). Таким образом, разрезав каёмку, Вася получит не более одной разноцветной доминошки.

Итак, докажем связность множества белых клеток каёмки. Клетки белого многоугольника образуют связное по сторонам множество клеток, поэтому достаточно доказать, что если между некоторыми двумя различными не соседними белыми клетками в каёмке есть путь по белым клеткам, не содержащий других клеток каёмки, то между ними есть и путь по белым клеткам каёмки, далее это и докажем. Клетки пути разбивают прямоугольник на две (необязательно связные по сторонам) части, между которыми нет путей по клеткам, не содержащих клеток пути . Значит, разбивает каёмку на две связные части, только в одной из которых могут быть чёрные клетки (так как чёрные клетки сами образуют связное по сторонам множество клеток, не содержащее клеток пути ). Следовательно, одна из частей каёмки полностью белая, и поэтому между рассмотренными белыми клетками каёмки есть путь по белым клеткам каёмки.

Первое решение.

Пусть — массы кусков в граммах. Упорядочим их по величине: Тогда , иначе кучка из одного куска массой и кучка из всех остальных кусков противоречат условию.

Теперь достаточно показать, что Предположим противное: пусть тогда (иначе снова есть две кучки, противоречащие условию: кучка из кусков массами и кучка из всех остальных кусков). Поэтому

Будем теперь класть на весы по одному куски массами именно в этом порядке. Начальная масса кучки на весах будет равна а конечная — так как

Поскольку масса каждого очередного куска меньше г, в некоторый момент на весах окажется кучка, масса которой будет не меньше г, но не больше г, что противоречит условию.

Второе решение.

Из условия следует, что масса каждого куска меньше г. При любом разбиении кусков на две кучки масса одной из них будет меньше г, а масса другой — больше г. В первом случае назовём кучку лёгкой, а во втором — тяжёлой. Лёгкой кучке соответствует тяжёлая (из остальных кусков), и наоборот. Также назовём произвольный кусок большим, если при добавлении его к некоторой лёгкой кучке она становится тяжёлой, а в противном случае назовём кусок маленьким (при добавлении его к любой лёгкой кучке она остаётся лёгкой). Масса любого большого куска больше г.

Рассмотрим кучку, состоящую из всех маленьких кусков. Она лёгкая, поэтому ей соответствует тяжёлая кучка из остальных кусков. В этой тяжёлой кучке не менее двух кусков, причём они все большие. Выберем один из этих кусков и переложим к кучке из маленьких кусков. Полученная кучка также лёгкая, так как её можно получить, добавляя последовательно к этому большому куску все маленькие куски. Ей снова соответствует тяжёлая кучка, также состоящая из не менее двух кусков. Таким образом, найдены три больших куска, любые два из которых образуют тяжёлую кучку, т.е. имеют суммарную массу больше г.

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

Пусть — множество всех последовательностей из нулей и единиц длины Определим функцию сопоставляющую каждой последовательности из последовательность, состоящую из её последних цифр. Пусть — множество всех последовательностей из нулей и единиц длины в которых ровно один элемент равен а остальные равны а — множество всех остальных последовательностей длины

Тогда Введём функцию нумерации для последовательностей из , т.е. функцию взаимно однозначно сопоставляющую каждой последовательности из какой-то номер от до Обе функции и известны как фокуснику, так и его помощнику.

Теперь опишем действия каждого из них. Пусть помощник увидел перед собой последовательность Тогда у него есть несколько вариантов:

1) Если то он сообщает значение элемента под номером

2) Если и первая цифра последовательности равна то помощник сообщает значение и номер единицы из последовательности

3) Если и первая цифра последовательности равна то помощник сообщает значение и номер того нуля, который следует за единственной единицей в последовательности (такая единица единственна, так как эта последовательность принадлежит множеству ). Если же единица стоит на последнем месте, то помощник сообщает значение и номер первого нуля.

Опишем действия фокусника.

1) Если он услышал цифру с номером из диапазона от до то он понимает, что это случай 1). Значит, по этому номеру с помощью функции нумерации (ввиду её биективности) он может восстановить а значит, и последние цифр вместе с их номерами.

2) Если он услышал цифру с номером из последних номеров, то он понимает, что это случай 2) или 3). Но в обоих случаях у нас у последовательности последние цифр все нули, кроме одного. Из последних цифр он может отгадать других цифры, так как одну уже назвал помощник. Также он может назвать самую первую цифру последовательности, так как она в случаях 2) и 3) совпадает с той цифрой, что называет помощник. Значит, и в этом случае фокусник отгадает цифр.

Первое решение.

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

Теперь каждую Васину группу (из двух клеток), совпадающую с какой-то из Петиных групп, покрасим в черный и белый цвет любым из двух способов - одну клетку в черный, другую в белый цвет.

Осталось раскрасить множество клеток, которое Васей и Петей разбито на пары так что ни одна Васина пара не совпадает с Петиной парой.

Построим граф, вершины которого соответствуют Васиным и Петиным группам (у Васи и Пети, очевидно, одно и то же количество групп). Две вершины соединим ребром тогда и только тогда, когда соответствующие группы имеют общую клетку. Тогда каждая вершина графа имеет степень два, причем любое ребро соединяет одну из вершин, соответствующих Васиным группам, с одной из вершин, соответствующих Петиным группам.

Такой граф разбивается на циклы, причем каждый цикл имеет четную длину (за счет того, что в нем чередуются вершины, соответствующие Васиным и Петиным групам) и допускает раскраску в два цвета, при которой цвета ребер чередуются вдоль цикла. Наконец, цвету клетки сопоставим цвет ребра, соединяющего две вершины графы, соответствующие Васиной и Петиной группам, пересекающимся по данной клетке. Полученная раскраска удовлетворяет условию задачи.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение.

Для удобства назовём непересекающиеся группы клеток одного разбиения (Пети или Васи) фигурками.

Построим вспомогательный двудольный граф G. Для каждой из фигурок одного из разбиений (Пети или Васи) добавим в граф новую, соответствующую этой фигурке вершину. При этом вершины, соответствующие фигуркам Пети, отнесём к первой доле, а вершины, соответствующие фигуркам Васи, - ко второй. Далее проведём рёбра между некоторыми вершинами графа по следующему правилу: если фигурка Пети пересекается с фигуркой Васи по нечётному количеству клеток, то проведём между соответствующими этим фигуркам вершинами ребро.

Заметим, что в построенном графе степень каждой вершины чётна. Действительно, выберем, например, произвольную фигурку Васи . Поскольку состоит из чётного числа клеток и пересекается лишь с фигурками из разбиения Пети, то по нечётному количеству клеток она будет пересекаться с чётным количеством фигурок.

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

Теперь построим искомую раскраску фигурок в разбиении Пети. Выберем произвольный цикл из построенного разбиения и ориентируем его рёбра в каком-то из двух возможных естественных направлений его обхода. Рассмотрим произвольное (уже ориентированное) ребро цикла . Пусть оно соединяет вершины, соответствующие фигуркам и . По построению фигурки и пересекаются по нечётному количеству клеток. Пусть они пересекаются по клетке. Тогда если ребро ведёт из первой доли во вторую, то Петя покрасит произвольные из них в чёрный цвет и произвольные из них в противном случае. Пусть Петя выполнит аналогичную покраску для каждой компоненты связности . Наконец, пусть для каждой пары фигурок и , пересекающихся по чётному количеству клеток, Петя покрасит ровно половину клеток в их пересечении в чёрный цвет.

Докажем, что полученная покраска будет искомой. Рассмотрим, например, произвольную фигурку Пети . Пусть - произвольная фигурка Васи. Заметим, что среди общих клеток фигурок и разность числа чёрных и белых клеток равна или 0 , в зависимости от чётности числа клеток в этом пересечении. Поэтому достаточно доказать, что разность +1 встречается среди пересечений фигурки Пети с фигурками Васи столько же раз, сколько и разность -1 . Пусть фигурке в графе соответствует вершина , которая лежит в некотором цикле из построенного ранее разбиения . Тогда каждой разности +1 соответствует ребро цикла , входящее в , а каждой разности -1 - ребро цикла , исходящее из . Из построения цикла следует, что рёбер, входящих в , в нём будет столько же, сколько и рёбер, исходящих из . Поэтому фигурок Васи, в клетках пересечения с которыми будет ровно на одну чёрную клетку больше, будет столько же, сколько фигурок Васи, в клетках пересечения с которыми будет ровно на одну белую клетку больше. Таким образом, в фигурке поровну чёрных и белых клеток.

Пусть в турнире участвовало команд. Заметим, что в каждом матче две команды в сумме получают 2 или 3 очка. Значит, общее количество очков, которые могут набрать все команды в одном круге, не меньше, чем , и не больше, чем . Из условия следует, что все команды вместе набрали в первом круге ровно в полтора раза больше очков, чем во втором ( всех очков в первом круге и во втором). Но это возможно лишь в случае, если в первом круге все матчи закончились победой одной из команд (общая сумма очков ), а во втором - ничьей (общая сумма очков ). Значит, победитель набрал во втором круге очков. По условию, , откуда находим .

Первое решение.

Рассмотрим всевозможные мелодии из нот до и си длины , коих штук. Каждую такую мелодию периодически продолжим в обе стороны, получив бесконечную в обе сторону мелодию. Назовём две получившиеся бесконечные мелодии эквивалентными, если одна получается из другой сдвигом.

Наименьший период всех бесконечных мелодий, кроме двух, состоящих только из нот до и только из нот си, равен Количество не эквивалентных друг другу бесконечных мелодий равно

(каждой бесконечной мелодии периода эквиваленты мелодий (включая саму с периодом, который будет циклическим сдвигом нот, дающих мелодию )

Из них мелодий, содержащих запрещённые Кощеем мелодии, не больше

(в скобках учтены запретные мелодии длины , полученные дописыванием символов к запретной мелодии длины , а за скобками — все остальные).

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

______________________________________________________________________________________________________________________________________________________

Второе решение.

Пусть - число мелодий длины , не содержащих запретных последовательностей нот. Будем считать, что По индукции докажем, что для всех натуральных .

База индукции

Предположим, что неравенство верно для всех , меньших Покажем, что тогда Заметим, что

Действительно, мы можем добавить в конец ноту двумя способами к уже имеющейся незапрещенной мелодии из нот. При добавлении ноты могла возникнуть запретная мелодия длины в конце последовательности, однако она "испортит"максимум последовательности нот, так как первые ноты до "запрещенной"мелодии - незапрещенная мелодия длины . Аналогично могли получить запретную последовательность из нот и испортить разрешённую мелодию из нот и т. д. (Здесь мы можем вычесть лишнее, если , и часть вычитаемых мелодий могут быть одинаковыми, но поскольку мы пишем оценку снизу, всё правильно.)

Из предположения индукции для также следуют неравенства:

Применим эти следствия, а также неравенство выше, для доказательства перехода индукции и получим:

Следовательно, и переход доказан.

Тогда из-за положительности последовательность возрастающая, а значит , откуда следует, что Иван справится с испытанием Кощея.

Докажем, что для любого натурального первый игрок на своём -ом ходе может добиться, чтобы количество забранных из кучки камней равнялось , и второй игрок не сможет ему помешать. Доказательство проведём индуктивно.

В свой первый ход первый игрок забирает один камень, т. е. число забранных камней равно . Пусть в свой -й ход первому игроку удалось сделать так, чтобы количество забранных камней равнялось . В свой -й ход второй игрок может взять от до камней. Поскольку после его хода общее количество забранных камней будет больше и меньше . Первый игрок в свой следующий ход может взять от до камня и точно сможет получить забранных камней независимо от предыдущего хода второго игрока.

Таким образом, поскольку , побеждает первый игрок: ему достаточно каждый раз забирать такое число камней, чтобы общее число забранных камней было точным квадратом, и на своём ходе он возьмёт последний камень.

В последний день все упорные выиграли. Значит, их не больше половины. Если их меньше половины, то каждый день была встреча между неупорными игроками. Остаётся рассмотреть случай, когда количество упорных составляет половину от общего числа игроков Такой турнир длился дней, и нужно доказать, что было хотя бы дней, когда была встреча между неупорными. Это равносильно тому, что было хотя бы дней, когда была встреча между упорными, так как и тех и других — ровно половина (если все упорные играют только с неупорными, то в этих встречах участвуют все неупорные, и обратно).

Предположим противное: пусть встречи между неупорными игроками проходили менее, чем в половине всех дней турнира. Тогда, в силу замечания выше, то же самое можно сказать и про встречи между упорными игроками. Так как всего упорных игроков каждый упорный играл с упорными день. Поэтому единственный возможный вариант, при котором встречи между упорными игроками проходили менее чем в половине дней турнира, — это когда все упорные играют между собой в одни и те же дни. Другими словами можно сказать, что упорные проводят в этот день между собой минитурнир, а такое возможно только если число упорных игроков чётно. Вспомним теперь, что то есть а поскольку — чётное, то Тогда в первый из дней минитурнира играли по крайней мере две пары упорных игроков, а значит было хотя бы два упорных, победивших в этот день. В дальнейшем они должны сыграть между собой, но тогда один из них проиграет после того, как выиграл. Противоречие. Значит, наше предположение неверно, и игровых дней, когда была встреча между неупорными игроками, не менее половины.

Цифры и уже участвуют в номере года, поэтому из всех месяцев нужно рассмотреть только и В каждом из этих номеров есть поэтому в красивой дате не будет дня с номером, начинающимся с и а также не будет дней и — остаются только дней, с по Но тогда в каждом месяце красивая дата начинается с и подходят только месяцев, с по Остаётся заметить, что для каждого подходящего месяца ровно один день, оканчивающийся на ту же цифру, не будет красивым — значит, в каждом из месяцев по красивых дат, а всего в году —

Рассмотрим команды и одержавшие одинаковое число побед, и пусть в матче между ними победила команда Покажем, что обязательно найдется команда которая выиграла у команды но проиграла команде Рассмотрим все команды, у которых выиграла команда Среди них найдётся хотя бы одна команда, которая выиграла у команды так как в противном случае с учётом выигрыша у команды команда набрала бы больше очков, чем команда Таким образом, тройка команд удовлетворяет условию задачи.

Поскольку количества колпаков различных цветов принимают все значения от 0 до 24.

Далее, каждый мудрец считает количество колпаков каждого из цветов. Для двух цветов количества колпаков совпадают и мудрец понимает, что на нём колпак одного из этих двух цветов. Остаётся только сделать выбор, какой именно из этих двух цветов ему назвать.

Инверсией в перестановке называется всякая пара индексов такая, что и Чётность числа инверсий в перестановке определяет чётность перестановки. Стратегия, приведённая ниже, основана на понятии чётности перестановки.

Пусть мудрецы заранее занумеровали цвета числами от 0 до 24. Тогда истинному распределению колпаков соответствует перестановка

Если мудрец видит равное количество колпаков цвета и цвета (по штук каждого из этих двух цветов), то ему нужно принять решение, к какому из этих двух цветов отнести свой колпак, то есть выбрать между двумя перестановками

Одна из этих перестановок соответствует истинному распределению цветов, при этом указанные перестановки отличаются расположением ровно двух элементов, поэтому имеют разную чётность.

Мудрецы могут заранее договориться, чтобы ровно 150 из них сделали свой выбор в пользу чётной перестановки, а остальные 150 — в пользу нечётной перестановки.

Тогда ровно 150 мудрецов верно назовут цвет своего колпака.

Пусть в равнобедренной трапеции с основаниями проведена диагональ так что первый жук ползает по циклу второй — по циклу

Рассмотрим моменты времени, в которые первый жук оказывается в точке За время обхода первым жуком полного цикла из снова в второй жук сдвигается по своему циклу на в одну и ту же сторону. Поскольку

при таких сдвигах в один из рассматриваемых моментов времени второй жук окажется на расстоянии меньше до точки по ходу своего движения, а значит, встретится с первым жуком на диагонали

Для описания отправляемых в лабораторию смесей составим таблицу, состоящую из строк и столбцов. Каждый столбец таблицы — это описание состава смеси, отправляемой в лабораторию. На пересечении -й строки и -го столбца стоит единица, если -я смесь содержит жидкость из -й пробирки, и ноль в противном случае.

Сначала попробуем найти пару пробирок с ядом и противоядием, не устанавливая, где в этой паре яд, а где противоядие. Для этого огрубим результат лаборатории, убрав из него знак (то есть будем считать, что для каждой смеси лаборатория сообщает результат если в смеси есть яд без противоядия или противоядие без яда, и ноль иначе). Pacсмотрим две строки, соответствующие пробиркам с ядом и противоядием. Их покоординатная сумма, взятая по модулю совпадает со строкой результатов, присланных лабораторией. Следовательно, если все суммы пар строк таблицы, взятые по модулю будут попарно различны, то в результате тестирования мы сможем определить номера строк, соответствующих яду и противоядию.

Такую таблицу можно построить следующим образом. Первую ее строку заполним произвольно. Вторую строку заполняем так, чтобы она не совпадала с первой. Третья и все последующие строки должны удовлетворять двум условиям:

- новая строка не должна совпадать с уже заполненными;

- новая строка должна быть такой, чтобы суммы всех возможных пар построенных строк, взятые по модулю были различны.

Покажем, что построение возможно. Покоординатную сумму строк и взятую по модулю будем обозначать как Рассмотрим строчки и Предположим, что тогда

Следовательно, правила построения таблицы можно переформулировать следующим образом:

- новая строка не должна совпадать с уже заполненными;

- новая строка должна быть такой, чтобы она была отлична от всех возможных сумм троек уже построенных строк.

Число строк длины составленных из нулей и единиц, равно Запретов, даже после заполнения всех строк, будет не более чем

Следовательно, такую таблицу можно построить.

Чтобы определить пару пробирок с ядом и противоядием, найдем все попарные суммы строк таблицы, взятые по модулю Найдем такие строки и что совпадает с огрубленным результатом лаборатории. Пробирки, соответствующие строкам и содержат яд и противоядие. Далее, рассматривая уже настоящий результат лаборатории, мы сможем точно сказать, в какой пробирке яд, a в какой противоядие. Действительно, обязательно найдется хотя бы одна смесь, содержащая либо только яд, либо только противоядие, иначе строки таблицы, соответствующие пробирке с ядом и пробирке с противоядием, будут одинаковыми, что запрещено построением. Тогда по знаку результата для этой смеси мы сможем определить, был в ней яд или противоядие.

Если Полина возьмёт себе все черви, все тузы, всех королей и всех дам, то Василиса не сможет набрать очки на тузе, короле и даме червей, т. е. наберёт не больше очков.

Теперь докажем, что при любом выборе Полины Василиса может заработать не меньше очков. Выложим карты в клетки таблицы (в одном столбце карты одного достоинства, в одной строке — карты одной масти). Докажем, что если Полина закрасила черным клеток, то Василиса может выделить не менее непересекающихся xороших пар: в каждой паре две клетки разного цвета, находящиеся в одной строке или одном столбце. (Тогда Василиса на ход одной картой из пары сможет отвечать ходом второй карты из этой пары и заработать очков.)

Назовём типом столбца количество чёрных клеток в нём. Сначала Василиса рассматривает столбцы типа (если они есть). Каждый из них, очевидно, разбивается на две хорошие пары.

Далее Василиса рассматривает пары столбцов типа и Каждая такая пара, очевидно, разбивается на четыре хорошие пары клеток.

Далее Василиса рассматривает пары столбцов типа и Каждая такая пара тоже разбивается на четыре хорошие пары клеток (см. рисунок слева).

Когда указанные пары столбцов закончатся, в силу симметрии можно считать, что “необработанными” останутся только столбцы типов и Если это столбцов типа и столбцов типа то т. е. В тройке из столбца типа и двух столбцов типа Василиса сможет выделить не менее пяти хороших пар клеток (см. рисунок справа).

Так как то на всей доске останется не более трёх нехороших пар, т. е. Василиса «потеряет» не больше очков.

Рассмотрим множество клеток которое является вертикальным отрезком длины Заметим, что каждый столбец пересекает по или клеткам, а каждая строка или диагональ по или клетке.

Рассмотрим множество которое состоит из копий отрезка каждая из которых получается из предыдущей переносом на вектор Таким образом, состоит из отрезков длины разделенных пустыми столбцами. Заметим, что любая строка или столбец пересекают по или клеткам, а каждая диагональ — по или клетке (так как никакая диагональ не пересекает две копии в

Множество состоит из копий каждая из которых получается переносом предыдущей на вектор Любая строка, столбец или диагональ, параллельная вектору пересекает не более одной копии в а любая диагональ, параллельная вектору либо не пересекает ни одной, либо пересекает все копии в Следовательно, строки, столбцы и диагонали, параллельные вектору пересекают или клеток из а диагонали, параллельные вектору пересекают или клетку.

Аналогично построим множество оно состоит из копий каждая из которых получается переносом на вектор из предыдущей. Любая строка, столбец или диагональ, параллельная вектору пересекает не более одной копии в а любая диагональ, параллельная вектору либо не пересекает ни одной, либо пересекает все копии. Следовательно, любая строка, столбец или диагональ пересекает по или клеткам.

Каждый двухклеточный прямоугольник содержит чёрную и белую клетки, поэтому если вырезано 9 белых клеток, то больше прямоугольников вырезать не получится.

Разрежем доску так, как показано на рис. 1. Вырезанные из доски клетки при разрезании “испортят” не более 10 прямоугольников. Следовательно, у нас уже есть по крайней мере 22 целых прямоугольника. Покажем, как увеличить количество целых прямоугольников на 1. Рассмотрим изображённую на рис. 1 замкнутую цепочку клеток (по цепи идём от клетки а2 вверх). Поскольку вырезаны как белые, так и чёрные клетки, в этой цепи обязательно есть вырезанная белая клетка, за которой идёт вырезанная чёрная клетка.

Если эти клетки соседние, то они “портят” только один прямоугольник, значит, при таком разрезании будет не менее 23 целых прямоугольников.

В противном случае, если между ними есть ещё клетки, разделим доску между ними так, чтобы новый прямоугольник начинался сразу после вырезанной белой клетки (см. рис. 2). Тогда количество целых прямоугольников увеличится на 1. Следовательно, опять будет не менее 23 целых прямоугольников.

Рассмотрим произвольную расстановку чашек и выпишем в строчку их цвета. Под этой строчкой выпишем также все её различные циклические сдвиги — всего штук. Подсчитаем, сколько всего будет совпадений по цвету на одной и той же позиции в исходной расстановке и в расстановках, полученных сдвигами. Для чёрных чашек совпадения по цвету будут ровно в сдвигах, а для белых — в сдвигах. Следовательно, всего совпадений по цветам для сдвигов будет

Значит, существует сдвиг, в котором будет не более совпадений с исходной расстановкой.

Рассмотрим такую расстановку чашек:

Непосредственной проверкой можно убедиться, что все её циклические сдвиги имеют с ней ровно совпадений.

Первое решение.

Сначала покажем, что расстояние до ближайшего целого числа от числа вида (где — иррациональное и — любое фиксированное число) можно выбором сделать сколь угодно малым.

Рассмотрим чисел

Их дробные части попадают в один из промежутков

Тогда по принципу Дирихле найдутся два числа

дробные доли которых попали в один и тот же промежуток. Их разность

также является числом вида причём, поскольку разность их дробных частей по модулю меньше для некоторого целого верно неравенство

Следовательно, существует такое число

что

Выберем натуральное число так, что выполняется одно из двойных неравенств

(здесь обозначает дробную часть ). Тогда найдётся такое целое число что

т.е.

Следовательно,

где

Значит, расстояние от целого числа до числа меньше Увеличивая значение можно сделать это расстояние сколь угодно малым.

Без ограничения общности будем считать, что При преобразовании подобия прямой с коэффициентом точка перейдёт в точку а точка — в точку Кузнечик теперь будет прыгать на вправо и на влево. В некоторый момент кузнечик пересечёт середину отрезка прыжком на вправо и попадёт в некоторую точку После этого кузнечик никогда не будет делать прыжки длины более одного раза подряд. При прыжке на дробные доли точек, в которых кузнечик находился до и после прыжка, одинаковые.

Пусть кузнечик находится в точке Выберем такое натуральное число что расстояние от до ближайшего целого меньше Если кузнечик сделает прыжков влево, он будет находиться на расстоянии менее от какого-то целого числа, независимо от того, сколько при этом он совершил прыжков вправо на Поскольку точка находится левее середины нашего отрезка, то, прыгая на вправо, кузнечик обязательно окажется на расстоянии менее от точки а на исходной прямой — на расстоянии, меньшем от точки

Второе решение.

Независимо от своего начального положения кузнечик рано или поздно окажется на промежутке

Действительно, если то он будет прыгать вправо на , пока не перепрыгнет точку и не окажется на промежутке

А если то он будет прыгать влево на пока не перепрыгнет точку и не окажется на промежутке

При дальнейших прыжках кузнечик уже не покинет промежутка оказавшись на он прыгает влево на и попадает на а оказавшись на он прыгает вправо на и попадает на

Если склеить промежуток в окружность той же длины то указанные прыжки кузнечика на этой окружности будут уже прыжками в одну сторону на (или в другую сторону на что на данной окружности — одно и то же).

Поскольку отношение прыжка к длине окружности иррационально, следы кузнечика будут всюду плотны на окружности, то есть рано или поздно кузнечик попадёт на всякую дугу окружности. Следовательно, и на исходном промежутке следы кузнечика всюду плотны, так что рано или поздно он попадёт в любую наперед заданную окрестность нуля.

Первое решение. Предположим, что такого треугольника не существует, и докажем, что существует прямая, все точки которой имеют один цвет.

Пусть на некоторой прямой есть две точки одного цвета (обозначим этот цвет расстояние между которыми равно Пусть — две прямые, параллельные и удаленные от нее на расстоянии Если на какой-нибудь из этих прямых есть точка цвета то она образует с точками треугольник площади все вершины которого имеют одинаковый цвет. Если на каждой из прямых присутствуют два цвета и на одной из них найдутся две точки одного цвета на расстоянии то они вместе с точкой такого же цвета на другой прямой образуют треугольник площади все вершины которого имеют одинаковый цвет. Если же на каждой из прямых присутствуют два цвета и любые две точки на расстоянии разных цветов, то любые две точки на расстоянии будут одного цвета, а значит, на прямой все точки имеют цвет

Пусть теперь все точки некоторой прямой покрашены в цвет Тогда остальные точки плоскости покрашены в два оставшихся цвета. Возьмем прямую, не параллельную и две точки на ней одного цвета (обозначим этот цвет Если на какой-нибудь из двух прямых, параллельных и удаленных от нее на расстояние найдется точка цвета то и эта точка образует треугольник площади все вершины которого имеют одинаковый цвет. Если же таких точек нет, то найдется треугольник площади с вершинами цвета

______________________________________________________________________________________________________________________________________________________

Второе решение. Пусть не все точки плоскости раскрашены в один цвет. Тогда на некоторой прямой присутствуют точки разных цветов: точки и цвета и точка цвета Пусть — прямоугольник, в котором середины сторон соответственно, длины этих сторон равны — середины п соответственно, — точка, симметричная относительно

Если среди точек есть точка цвета она образует искомый треугольник с точками Если среди точек нет точек цвета то возможны следующие случаи.

1.

Точки и (рассуждение для точек и аналогичны) разного цвета. Тогда цвет совпадает с цветом одной из них, например, Если какая-то из точек того же цвета, эти три точки образуют искомый треугольник. В противном случае искомым будет треугольник

2.

Если одна из пар или цвета она образует искомый треугольник с точкой

3.

Если все точки цвета и одна из точек тоже цвета то треугольник или искомый. В противном случае треугольник искомый.