Петя и Вася играют в следующую игру. У них есть клетчатый прямоугольник 1000 × 2020, первым ходит Петя. Своим ходом первый игрок делит прямоугольник на два меньших одним разрезом вдоль линии сетки. Затем второй игрок выбирает один из двух получившихся прямоугольников, на котором будет продолжаться игра (второй прямоугольник отбрасывается), и делит его на два меньших. Потом опять первый выбирает прямоугольник, на котором будет продолжаться игра, и т. д. Проигрывает тот, кто не может в свой ход разрезать прямоугольник. Кто из игроков может всегда выигрывать, как бы ни играл его соперник?
Решение. Докажем более общий факт: Петя имеет выигрышную стратегию только при таких m и n, у которых различается степень вхождения двойки в разложении на простые множители (соответственно, если степени вхождения двойки в m и n одинаковы, то выигрышная стратегия есть у Васи). Поскольку 1000 делится на 8, а 2020 не делится на 8, отсюда последует ответ задачи.
На каждом ходу стороны прямоугольника будем записывать следующим образом: 
и 
где m1 и n1 — нечётные числа; a и b — целые неотрицательные числа (стороны прямоугольника будем обозначать всегда m и n, в процессе игры они будут меняться). Ситуацию 
будем называть хорошей, а ситуацию 
— плохой (соответствующие прямоугольники будут также хорошими и плохими). Докажем, что в хорошей ситуации выигрышную стратегию имеет Петя, а в плохой — Вася.
Рассмотрим плохую ситуацию. Докажем, что как бы ни разделился прямоугольник в этом случае, соперник сможет выбрать себе такой прямоугольник, чтобы у него была хорошая ситуация. Предположим, получилось разрезать так, что оба получившихся прямоугольника плохие, т. е. они представимы в виде 
и 
где m1, k, l — нечётные числа (не умаляя общности, разрезалась сторона n). Но тогда до разрезания сторона n прямоугольника равнялась 
что делится на 
т. к. k и l нечётны. Но начальная ситуация была плохой и длина стороны n делилась только на 2a, противоречие.
Рассмотрим хорошую ситуацию. Не умаляя общности, пусть 
Скажем, что игрок в данной ситуации должен разделить прямоугольник на 
и
Заметим, что все длины делятся на 2a и не делятся на поэтому, какой бы прямоугольник ни выбрал соперник, у него будет плохая ситуация.
Приведём стратегию для обоих игроков. Если у Пети хорошая ситуация, он должен разделить прямоугольник так, чтобы у Васи ситуация стала плохой (следовательно, когда он разделит прямоугольник, Петя вернёт себе хорошую ситуацию и продолжит действовать аналогично). В случае когда у Пети плохая ситуация, по такой же стратегии может действовать Вася. Получаем, что игрок, находящийся в хорошей ситуации, всегда может сделать ход и гарантировать, что на следующем его ходу ситуация будет хорошей. Осталось заметить, что с каждым ходом прямоугольник уменьшается, и игра обязательно закончится, а нельзя сделать разрез только в прямоугольнике 1 × 1, что является плохой ситуацией.
Ответ: Петя.
Критерии проверки:Используется один наибольший подходящий критерий:
1) любое полное решение задачи — 7 баллов;
2) присутствует идея представления длин сторон прямоугольника в виде чисел 
где k — нечётное — 2 балла;
3) есть верный ответ — 0 баллов.
Ответ: Петя.
PDF-версии: 