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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

что

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

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

т.е.

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

где

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

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

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

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

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

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

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

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

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

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

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

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

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

______________________________________________________________________________________________________________________________________________________

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

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

1.

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

2.

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

3.

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть внутри страны, пока ещё не поделённой на губернии, возникла автономная область, состоящая из одного города. Эту область, во-первых, можно разделить на три губернии (две пустые), и во-вторых, она удовлетворяет условию как самостоятельная страна, то есть при удалении всех остальных городов. Будем добавлять города к автономной области с сохранением этих двух условий.

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

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

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

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

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

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

Когда число посчитанных узников становится равным “счётчик” говорит, что все узники уже побывали в комнате.

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

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

Индукция по толщине колоды. База (колода из одной карты) очевидна.

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

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

Цвета, в которые покрашен граф, занумеруем от до Те вершины цвета которые не соседствуют ни с какими вершинами цвета перекрасим в цвет Новая раскраска будет правильной, поэтому в ней цветов. Значит, какие-то вершины цвета не перекрашены и потому соседствуют с вершинами цвета Аналогично, вершины цвета которые не соседствуют с вершинами цвета перекрасим в цвет и т. д. вплоть до последнего цвета.

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

Решим сначала более простую задачу. Пусть банкир разрешает класть на весы монеты не более раза. Из какого наибольшего числа монет можно выделить более легкую за взвешиваний?

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

Если весы не в равновесии, то фальшивая монета очевидна. А если в равновесии, то количество подозрительных монет уменьшится на Следовательно, при взвешиваниях можно выделить фальшивую из монет.

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

Если весы в равновесии, то получаем исходную задачу для монет, не попавших на весы (их ), и взвешивания, значит,

Отсюда

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

Поскольку, как легко проверить, имеем по формуле для суммы арифметической прогрессии.

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

Сделаем несколько замечаний, каждое из которых очевидно.

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

Через целое число часов положение минутной и секундной стрелок будет таким же.

Заметим, что через 6 часов после каждого плохого момента будет хороший (так как часовая стрелка повернется на и попадет из плохого сектора в хороший).

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

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

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

Cнова переведём самого “дружелюбного” и самого “нелюдимого” в другой класс и т. д. Повторяя эти рассуждения раз, мы переведём в другой класс пар школьников, в каждой из которых ровно один Петин друг. Итак, друзей у Пети

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

отсюда будет следовать:

т.е. что противоречит условию задачи.

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

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

а из первой тройки:

Отсюда вытекает первое утверждение: Теперь рассмотрим тройку которая также представительна. Подставляя вместо получим представительную тройку Сравнение этих троек приводит ко второму утверждению:

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

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

• Не совпадают с так как и (иначе не был бы максимальным).
• По середине отрезка и одному из концов однозначно восстанавливается второй конец. Поэтому для любых середины отрезков (соответственно ) различны.
• Для любых середины отрезков различны: если бы они совпадали в точке то по неравенству треугольника откуда или

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

Индукция по числу городов.

База. Если в городе имеются всего два города и то утверждение очевидно: по условию из в ведут не менее двух дорог; поэтому достаточно установить по одной из этих дорог движение от к а по второй — от к мы сможем проехать от каждого города до любого, отличного от него.

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

Рассмотрим теперь новую страну, план которой получается из плана прошлой страны “склеиванием” всех городов нашего кольца в один город из которого исходят все дороги реально “упирающиеся” в кольцо Число городов такоой условной страны меньше поэтому по предположению индукции в нём можно ввести по всем дорогам одностороннее движение с соблюдением требований задачи. Если мы затем оставим движение по всем не входящим в кольцо дорогам таким же, каким оно было в этой новой стране, а по кольцу пустим движение в одном (безразлично каком!) направлении, то на всех городах страны будет установлено одностороннее движение — и притом с каждого города можно будет проехать в любой другой.