Применение классических комбинаторных методов к разным задачам

Отсортируем числа из множества по возрастанию:

Для любых трех последовательных чисел число по условию лежит в . Но

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

По условию числа , то есть , где - разность прогрессии.

и в силу того, что , а натуральное. Имеем единственное решение .

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

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

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

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

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

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

Турнир задается выбором ориентации ребер, которых . Поэтому всего турниров . Рассмотрим вероятностное пространство, элементами которого будут все турниры на вершинах, причем для различных ребер их ориентации независимы. Это означает, что все турниры равновероятны.

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

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

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

Первое решение. Индукцией покажем, что для городов База очевидна.

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Расположим наши числа по убыванию, Имеем

Умножим первое равенство на получим, что

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

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

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

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

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

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

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

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

______________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

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

Оценка.

Можно считать, что первый наклеенный кусок — весь квадрат, от этого ничего не испортится. Считаем его нулевым. Докажем индукцией по утверждение:

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

База при верна.

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

Пример.

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

Возьмём произвольное слово длины и будем последовательно передвигать в нем буквы A, не уменьшая при этом крутизну слова. Ясно, что в нашем слове должно быть хотя бы две буквы B, иначе крутизна слова равна Далее, предположим, что в слове между двумя буквами В есть буква А, т.е. слово имеет вид …В … …В …Посмотрим, с какой стороны от буквы больше букв А, и передвинем выделенную букву в тот конец слова, где их меньше. Заметим, что при таком перемещении буквы А мы могли разрушить лишь слова вида ABBA и ABBA, которые давали вклад в размер крутизны исходного слова. Предположим, что мы переместили букву К налево. Тогда слова вида BBA сохранились, а вместо слов вида ABB образованных буквой В слева от и двух букв В и буквы мы получим как минимум столько же слов, которые образуются из нашей передвинутой буквы двух любых букв У и любой буквы А, которая стояла в исходном слове справа от буквы А. Получается, что мы можем рассматривать только слова вида А...АВ...ВА...А. Если в левом блоке будет букв А, а в правом букв А, то крутизна такого слова равна

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

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

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

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

Замечание.

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

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

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

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

Отметим, что поскольку а в классах по учеников, то (и такой Петя найдется). Если условие не выполнено, то у Пети в Б классе не более (иначе вместе с Васей у них в этом классе есть общий друг). Значит, в А классе у Пети хотя бы друг, противоречие с выбором, который был ранее сделан.

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

что и требовалось доказать.

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

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

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

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

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

Сперва докажем следующую лемму.

Лемма. В ряд лежат апельсинов, массы любых двух соседних отличаются не более, чем на г. Тогда если упорядочить апельсины по убыванию массы, то массы любых двух соседних снова будут отличаться не более, чем на г.

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

Отметим на каждом пути из М в П первую дорогу числом Докажем, что на каждом пути осталось не менее неотмеченных дорог.

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

Отметим на каждом пути первую дорогу числом Теперь на каждом пути останется не менее дорог. Повторяя рассуждение, расставим отметки на каждом пути. Теперь раздадим дороги компаниям в соответствии с их “номерами”.

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

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

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

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

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

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

______________________________________________________________________________________________________________________________________________________

Лемма. Пусть мы провели сжатие фигуры или образа(далее фигуры). Тогда, если до сжатия была фигура то фигура заданная множеством будет гомотетична

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Из построения будет видно, что точка ого цвета после ого сжатия единственная.

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