Логика

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Оценка.

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

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

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

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

Пример.

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

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

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

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

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

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

Также заметим, что всего у доски будет узлов.

Тогда на доске можно разместить не более корабликов.

а) При получаем оценку, что кораблей не более

Так как число кораблей целое, то их максимум .

Пример на кораблей:

b) При , получаем оценку, что кораблей не более

Так как число кораблей целое, то их максимум .

Пример на кораблей:

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Пример: 28, 35, 36, ..., 42. Суммарное количество марок тут делится на 7 и на 8 ( ), поэтому можно сделать как 8 альбомов по 42 марки, так и 7 по 48 марок.

_________________________________________________________________________________________________________________________________________________________________________________

Итак, тогда общее число марок не меньше , к тому же кратно 7 и 8 , а потому не меньше . Если в этой сумме заменить на , то получим пример к ответу 32.

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

Если учеников три (или меньше), то учитель справится. Действительно, на первые два вопроса возможны 4 варианта ответа: ++, +-, –, -+. Поскольку учеников не больше трёх, то какую-то из этих комбинаций никто не выбрал, её-то учитель и объявляет «правильной». Так же он поступает с каждой следующей парой ответов. В результате у каждого ребёнка не больше половины верных ответов.

Четыре ученика смогут «обыграть» учителя. Для этого им надо разделить вопросы на две группы нечётного размера (например, первые 5 и последние 7 вопросов) и дать такие ответы: ++++++++++++,————, +++++——-,—–+++++++. Тогда найдётся ребёнок, угадавший больше половины ответов как в первой группе, так и во второй.