Шаг за шагом

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

1) Рядом с 2 стоит 3. Тогда рядом с 3 может стоять только 1. Ее сосед — это только 4 и рядом с 4 может встать только 6.

2) Рядом с 2 стоит 4. Тогда рядом с 4 может стоять или .

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

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

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

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

Самая большая степень двойки, не превосходящая 100, это . Фокусник в начале должен разбить пришедших на представление на циклы, длины одного из которых равна 64, а длины остальных — меньшие степени двойки, не важно какие. Тогда через 6 минут все шляпы окажутся у своих настоящих владельцев (у некоторых они окажутся раньше, но в этот момент это впервые произойдёт для всех сразу).

База для : Квадрат без угловой клетки является уголком из трёх клеток, поэтому база очевидна.

Переход:

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

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

Например, подходит . При этом , , , то есть это действительно три точных квадрата.

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

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

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

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

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

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

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

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

Комментарий. Таким образом можно получить пример на любое количество чисел.

Пронумеруем людей числами от до . Заметим, что при могут созвониться сначала и , потом и , потом и , и в конце и . Тогда все будут знать все новости. Пусть мы умеем организовывать созвон для человека. Научимся организовывать для . Сначала пусть созвонятся и . Теперь знает две новости. Далее организуем созвон для человека. А потом могут созвониться опять и . Легко видеть, что все будут знать все новости, а количество звонков стало равно .

Объединим сначала гирьки в пары: первая с последней, вторая с предпоследней и т. д. Получится 15 пар, каждая весом 31 г. Теперь достаточно разложить пары как угодно по 5 в кучку.

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

Решение

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

16 — это степень двойки. Решим эту задачу сначала для четырех чашек, потом для 8, потом для 16.

Разделим чашки на пары: 1-2, 3-4, 5-6, 7-8, 9-10, 11-12, 13-14, 15-16 и уравняем количества чая в каждой паре чашек. Теперь у нас две совершенно одинаковые восьмерки: 1, 3, 5, 7, 9, 11, 13, 15 и 2, 4, 6, 8, 10, 12, 14, 16. Уравняем количество чая в чашках первой восьмерки и точно таким же способом в чашках второй. Разделим эти чашки по парам (для первой восьмерки) 1-3, 5-7, 9-11, 13-15, получим 2 одинаковые четверки: 1, 5, 9, 13 и 3, 7, 11, 15. В каждой четверке разделим четыре чашки по парам и, уравняв количества воды в этих парах, сведем задачу к случаю двух чашек. Но в двух чашках количество воды можно уравнять по условию. Со второй восьмеркой чашек делаем точно так же.

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

Будем менять группы монет с разных чаш. Пусть у нас при каждой из следующих замен равновесие сохраняется. Поменяем по одной монете. Они одинаковы. Поменяем одну из этих монет с новой. Теперь три монеты одинаковы: пара на одной и одна — на другой чаше. Поменяем эту пару с парой еще нетронутых. Теперь на одной чаше пара одинаковых, на другой — тройка таких же монет. Поменяем тройку с тройкой нетронутых. Теперь на одной чаше тройка одинаковых монет, на другой — пять таких же монет. Продолжая в том же духе, после k-го шага получим на одной чаше одинаковых монет, а на другой — таких же монет, где — i-ое число Фибоначчи: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144. Итак, после 11-го шага на одной из чаш все монеты одинаковы. Но тогда они таковы же и на другой, что по условию невозможно.

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

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

Попробуем построить пример для четырёх дробей, пользуясь примером для трёх. Конечно, просто добавить к примеру ещё одну дробь мы не можем: сумма уже равна 1, добавление любой дроби увеличит эту сумму. Поэтому сначала поделим все дроби на 2 (числители так и останутся равны 1), а уже затем добавим к этим дробям новую дробь . Все дроби получились различны, и теперь ничего не мешает повторять этот процесс! Ещё раз общий шаг: делим все имеющиеся дроби на 2 и добавляем новую дробь . Сделав так 97 раз, получим 100 дробей, удовлетворяющих условию.

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