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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

______________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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