Задача 1: 25 школьников стоят в ряд. Самый левый школьник выше самого правого. Докажите, что найдется школьник, у которого левый сосед выше правого.

(А.~Храбров)

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

Задача 2: Найти все тройки простых чисел x,y,z, такие, что 19x – yz = 1995.

(Жюри)

Решение: Заметим, что yz = 19x – 1995 = 19(x – 105). Поскольку числа y и z – простые, то одно из них равно 19, а другое — (x – 105). Пусть, например, y = 19, z = x – 105. Тогда или x или z – четное число, а значит, z = 2, x = 107. Случай z = 19, y = 105 – x рассматривается аналогично. Ответ: x = 107, y = 19, z = 2 или x = 107, y = 2, z = 19.

Задача 3: В войске герцога Икторна 1000 гоблинов. Любые два гоблина либо дружат, либо враждуют, либо незнакомы. Гоблины – существа малообщительные, разговаривают только с друзьями. К тому же все они в плохом настроении, поскольку у каждого гоблина любые два его друга враждуют, а любые два врага дружат. Докажите, что для того, чтобы все войско узнало о предстоящем наступлении на Данвин, герцог должен сообщить об этом не менее чем 200 гоблинам.

(Р.~Семизаров)

Решение: Заметим, что никто из гоблинов не имеет больше двух друзей. Действительно, если какие-то трое дружат с одним и тем же гоблином, то они должны все враждовать между собой, что противоречит условию (двое, враждующие с третьим, должны дружить). Отсюда следует, что любой гоблин вместе со своими друзьями, друзьями своих друзей и так далее, образует цепочку (возможно, циклическую), в которой первый дружит со вторым, второй – с третьим и так далее. Рассмотрим фрагмент такой цепочки, состоящий из пяти гоблинов – A, B, C, D и E. Так как A и C – друзья B, они должны враждовать между собой; C и E – друзья D и тоже враждуют между собой. Значит, A и E дружат между собой, так как оба – враги C. Итак, каждый из этих пяти гоблинов уже имеет двоих друзей в той же компании, и следовательно, ни с кем больше не дружит. Таким образом, длина цепочки друзей не может быть больше пяти.

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

Задача 4: Клетчатый прямоугольник разрезали на прямоугольники 1 × 2 (доминошки) так, что любая прямая, идущая по линиям сетки, рассекает кратное четырем число доминошек. Докажите, что длина одной из сторон делится на 4.

(Д.~Карпов)

Решение: Для каждой прямой, идущей по линиям сетки, напишем число доминошек, которые она рассекает, и все выписанные числа сложим. Очевидно, сумма будет делиться на 4. Так как каждую доминошку рассекает ровно одна прямая, то полученная сумма равна общему числу доминошек. Итак, количество доминошек делится на 4, значит, площадь прямоугольника делится на 8. Поэтому длина одной из сторон делится на 4.

Задача 5: На экране калькулятора набрано число 1. Раз в секунду калькулятор производит следующее действие: если число на экране делится на 2^k, то калькулятор прибавляет к нему любое число от 1 до (k + 1). Докажите, что любая степень двойки когда-нибудь обязательно появится на экране.

(А.~Пастор)

Решение: Число 2 = 2¹ появится на экране в следующую же секунду. Допустим, что на экране никогда не появится 2ⁿ (n > 1). Пусть на экране набрано число m < 2ⁿ, оно делится на 2^l, и калькулятор собирается прибавить число a ≤ l + 1 так, что m + a > 2ⁿ. Поскольку l < n, то 2ⁿ – m делится на 2^l, а значит, a = 2ⁿ – m ≥ 2^l > l + 1. Противоречие.

Задача 6: Есть шоколадка 1995 × 1995 долек. Малыш и Карлсон играют в такую игру: ход состоит в том, что один из имеющихся прямоугольных кусков шоколада разламывают на две прямоугольные части, одну из которых можно после этого сразу же съесть (а можно и не есть). Проигрывает тот, кто не может сделать ход. Первым ходит Карлсон. Кто выиграет при правильной игре?

(А.~Пастор, Д.~Карпов)

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

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

Задача 7: На двух полках стоит в беспорядке многотомная энциклопедия «Все о собаках». Самым левым на верхней полке стоит том «Моськи». Каждое утро библиотекарь меняет местами два тома с соседними номерами, стоящие на разных полках. В один прекрасный день все тома вернулись на исходные полки. Докажите, что «Моськи» по-прежнему стоят слева на верхней полке.

(К. Кохась)

Решение: На самом деле все тома вернутся на свои места. Действительно, заметим, что если номер тома, стоящего на полке на i-ом месте был меньше номера тома, стоящего на j-ом месте этой же полки, то он останется меньше и после выполнения указанной операции. Это следует из того, что при выполнении операции мог измениться только один из этих номеров, да и то не настолько, чтобы «перескочить» через другой, а всего на 1. Значит, когда тома вернутся на исходные полки, их порядок будет тем же. (А где иначе, по-вашему, стоит том с наименьшим на этой полке номером? А со следующим по величине номером?)