Логика

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

Предположим противное. Тогда сумма всех чисел в тетрадке равна

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

Сначала сделаем оценку, затем приведём пример.

Оценка. Пусть числа …, равны …, в некотором порядке. Сумма всех этих чисел равна

откуда то есть откуда Мы получили, что обязано быть нечётным.

Пример. Расставим числа в порядке

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

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

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

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

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

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

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

а значит, вероятность выиграть больше

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

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

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

Легко видеть, что фиксированное животное из первого загона встретит животное того же вида ровно раз (то есть при поворотах карусели из ). Тогда суммарное количество встреч животных одного типа равно Тогда по принципу Дирихле при каком-то повороте количество встреч было не меньше, чем то есть при таком повороте не менее животных встретили животное того же вида.

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

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

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

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

получаем требуемое

Все сидящие за столом разбиваются на пары друзей; значит, рыцарей и лжецов поровну. Рассмотрим любую пару друзей. Если они сидят рядом, то рыцарь на заданный вопрос ответит “Да”, а лжец — “Нет”. Если же они не сидят рядом, то их ответы будут противоположными. В любом случае ровно один из пары друзей даст ответ “Да”. Значит, все остальные ответов будут “нет”.

Чтобы можно было однозначно определить, в какой из коробок лежит приз, требуется возможность получить хотя бы различных ответов на один набор вопросов. Так как ответы ведущего для различных положений приза могут отличаться только числом “да” среди них, то требуется возможность получить в ответ хотя бы различных количеств “да”. Значит, требуется хотя бы вопросов (от до “да”). Пример на вопросов. Пусть -ый вопрос: «Номер коробки, в которой лежит приз, меньше либо равен ?». Тогда если ответов “да” ноль, то приз в сотой коробке, если один, то в -й и т.д.

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

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

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

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

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

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

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

Вырежем из нашего куба куб и разобьём его на 64 куба .

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

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

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

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

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

Изначально такого множества точно нет. Рассмотрим первый момент, когда удалось про некоторое множество доказать, что в нем четное число рыцарей. Пусть последним ходом «Вжух!» говорил волшебник . Несложным переборов вариантов можно убедится, что на прошлом ходу симметрическая разность и тоже содержала четное количество рыцарей, что противоречит выбранному первому такому моменту.

_________________________________________________________________________________________________________________________________________________________________________________

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

Оценка.

Рассмотрим условие на первую коробку. Из него следует, что в первой коробке не синих шариков не больше двух: иначе мы могли бы набрать 3 шарика, среди которых нет синих.

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

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

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

Пример.

Положим в первую коробку 2 белых шарика и 2 синих, а во вторую 2 красных шарика и 3 белых. Нетрудно убедиться, что все условия выполняются.