Индукция в комбинаторике

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. На клетчатой плоскости закрашено клеток. Тогда есть не более квадратов содержащих хотя бы две отмеченные клетки.

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

База. Все клеток в одной строке. Если они стоят подряд, то есть в точности квадратов. А если не подряд, то ещё меньше.

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

_________________________________________________________________________________________________________________________________________________________________________________

Предположим, что цветов не менее Тогда по лемме есть не более квадратов содержащих две отмеченные клетки одного из цветов. Но всего в квадрате есть квадрат Противоречие.

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

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

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

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

Числа от 1 до 4 можно выписать по кругу четырьмя различными способами:

Хорошими в них будут единственные пары:

При этом База индукции выполнена.

Шаг индукции.

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

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

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

В итоге ответ — 97 хороших пар чисел.

_________________________________________________________________________________________________________________________________________________________________________________

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

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

Рассмотрим две хороших пары чисел в которых все 4 числа различны. Можно считать, что Если хорды, соответствующие этим парам, пересекаются по внутренней точке, то числа и лежат по разные стороны от хорды и оба больше что противоречит «хорошести» пары

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

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

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

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

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

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

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

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

Доказательство проведём индукцией по

База: Если у каждой последовательности есть хотя бы один сосед, то

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

Для любой последовательности

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

Таким образом, в своём подмножестве или последовательность имеет не менее соседей.

По предположению индукции: и Следовательно:

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

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

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

Если — нечётное, то после выкидывания числа по предположению индукции числа должны быть выписаны подряд от 1 до но тогда можно вставить только между двумя числами, дающими в сумме то есть между 1 и или между и Итого, два способа, переход доказан.

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

Покажем, что меньшего числа конфет может не хватить. На тот случай, если все участники решили поровну задач, число конфет необходимо сделать кратным 25. Пусть Представим себе, что 24 человека решили поровну, а 25-й решил меньше. Если каждому из первых 24 участников дать по конфет или еще меньше, то останутся лишние конфеты. Значит, каждому из них необходимо дать как минимум по конфете, откуда то есть и

Теперь докажем по индукции, что можно раздать участникам конфет так, чтобы каждый получил меньше конфет. База при очевидна: дадим единственному участнику 0 конфет.

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

конфет, и мы раздадим их поровну «верхним» участникам. Каждый из них получит по конфет. Это число не меньше, чем поэтому больше того, что мы раздали каждому из остальных. Кроме того,

что и завершает переход.

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

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

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

Таким образом, ответом на задачу является число

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

______________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

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

Оценка.

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

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

Пример.

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

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

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

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

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

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

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

______________________________________________________________________________________________________________________________________________________

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

Будем решать задачу для томов.

База для и Для расстановка верна. Для либо порядок уже верен, либо его можно изменить за один ход из в

Переход:

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

Значит, и 55 томов можно расставить.

База для очевидна.

Переход:

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

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

База для очевидна.

Переход: . Будем воспринимать лестницу из й ступеньки как лестницу из ступенек и ещё одной дополнительной ступеньки.

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

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

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

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

1.

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

2.

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

Пусть минимальное число шагов для перемещения башни из дисков равно Выразим через Рассмотрим башню из диска. Разобьём всю процедуру на три этапа.

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

Этап — от первого до последнего перемещения нижнего диска. Одного шага достаточно: после первого перемещения нижний диск можно больше не трогать.

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

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

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

Приведем пример на 175 чисел. Занумеруем строки числами от 1 до 100. В первой строке поставим числа от 1 до 10, а в строке с номерами от до поставим числа 1 до 5 и числа от до Тогда в каждой строке будет 5 уникальных чисел и еще числа от 1 до 5, т.е. ровно 10 различных чисел, а в каждых четырех строках будет ровно 15 различных чисел. Таким образом, в таблице будут числа от до

Замечание.

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

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

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

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