Вспомним формулу разности квадратов:

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

Если у них одинаковый остаток при делении на 100, то их разность делится на 100, поэтому и разность их квадратов делится на 100.

Иначе либо их сумма (если это два числа из первых 49 пар) делится на 100 (а значит, и разность квадратов делится на 100), либо (если это два числа из последней пары) одновременно их разность и сумма делятся на 50 (а значит, и разность квадратов делится на так что делится и на 100).

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Оценка.

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

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

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

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

Пример.

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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