Задача 161. Игра в «Камешки»-VI
Перед Андреем и Борисом лежат 2020 кучек по одному камушку. За один ход разрешается объединить две кучи с одинаковым числом камней в одну. Проигрывает тот, кто не может сделать ход. Кто выигрывает при правильной игре, если начинает Андрей?
Решение:
Заметим, что все кучки в любой момент времени содержат количество камешков равное некоторой степени двойки, так как каждая кучка получается несколькими объединениями (умножениями на два) кучек из 1 камня. Посмотрим на ситуацию, когда кто-то из игроков проигрывает, то есть когда нельзя уже сделать ход. В этот момент 2020 разбилось на несколько различных слагаемых — степеней двоек. Из двоичной системы счисления мы знаем, что любое число единственным образом представляется в виде суммы степеней двоек. Для 2020 это разложение — 1024+512+256+128+64+32+4. То есть в конце всегда остаются эти 7 кучек. Теперь заметим, что за каждый ход количество кучек уменьшается на 1 (две кучки объединяются в одну), то есть из 2020 получится 7 ровно через 2020-7=2013 ходов. Тогда последний ход сделает именно первый, он и победит.
Ответ:
Андрей
Задача 161. Игра в «Заполнение доски»-VI
Андрей и Борис играют в игру, по очереди зачеркивая клетки доски 3×101. Исходно на доске зачеркнута только центральная клетка. За один ход игрок должен выбрать диагональ (в диагонали может быть 1, 2 или 3 клетки) и зачеркнуть в ней все еще не зачеркнутые клетки. Каждым ходом должна быть зачеркнута хотя бы одна новая клетка. Проигрывает тот, кто не может сделать ход. Начинает Андрей. Кто из игроков может выиграть вне зависимости от ходов противника?
Решение:
Приведем одну из возможных стратегий за Бориса. Покрасим клетки доски в шахматном порядке так, чтобы угловые клетки были черными. В нечетных столбцах крайние клетки будут черными, а в четных белыми. Центральная клетка находится в 51-м столбце, поэтому она сама будет белой.
Каждая диагональ либо полностью черная, либо полностью белая. Обе стратегии будут симметричными, но разными для разных цветов. Для клеток белого цвета будем ходить симметрично относительно центрального столбца (осевая симметрия). Для черных клеток будем ходить симметрично относительно центральной клетки (центральная симметрия).
Докажем, что Борис всегда сможет сделать ход согласно стратегии. Для этого нужно убедиться, что своим ходом он будет зачеркивать хотя бы одну новую клетку. Для черных клеток две диагонали - выбранная Андреем и центрально-симметричная ей, выбранная Борисом не имеют общих клеток. При этом Андрей смог сделать ход, значит, на выбранной им диагонали была незачеркнутая клетка. Так как до хода Андрея ситуация для черных клеток была центрально-симметричной, на диагонали Бориса перед ходом Андрея тоже была незачеркнутая клетка. Андрей не мог ее зачеркнуть, значит, Борис своим ходом зачеркнет хотя бы одну новую клетку.
Для белых клеток ситуация несколько иная: две диагонали, проходящие через центральную клетку, симметричны относительно центрального столбца, но других симметричных белых диагоналей на доске нет. Опять же, перед ходом Андрея ситуация на белых клетках осе-симметрична, то есть и на диагонали, выбираемой сейчас Андреем, и на диагонали, выбранной по стратегии Бориса, есть незачеркнутые клетки. Но единственная общая клетка, которую могут иметь осе-симметричные белые диагонали, зачеркнута с самого начала, поэтому Андрей не может своим ходом зачеркнуть незачеркнутую клетку с диагонали Бориса. Таким образом, Борис своим ходом зачеркнет хотя бы одну новую клетку.
Итак, мы доказали, что у Бориса всегда есть ход согласно стратегии. Так как ходов конечно (игра закончится не позже, чем через 303 хода, когда точно будут зачеркнуты все клетки), Борис победит.
Ответ:
Борис
Задача 162. Игра в «Заполнение доски»-VII
В ряд выложены 2020 шариков. Андрей и Борис играют в игру, делая ходы по очереди, начинает Андрей. За каждый ход разрешается покрасить один из еще не покрашенных шариков в один из трёх цветов: красный, жёлтый или зелёный (в начале игры все шарики не покрашены). После того, как все шарики покрашены, победа присуждается Андрею, если в ряду найдутся три подряд идущих шарика трёх разных цветов; иначе победа присуждается Борису. Кто из игроков имеет выигрышную стратегию?
Решение:
Для победы Борису достаточно добиться того, чтобы у каждого шарика был соседний того же цвета. Для этого поделим шарики на пары — (1,2), (3,4), …(2019, 2020). Андрей начинает и красит какой-то шарик из пары, после чего Борису нужно покрасить второй шарик из пары в тот же цвет, что всегда можно сделать, действуя по такой стратегии.
Ответ:
Борис
Задача 163. Игра в «Заполнение доски»-VIII
Двое игроков, Андрей и Борис, по очереди ставят шахматные ладьи на клетки доски 11×11, начинает Андрей. Запрещено ставить ладью, если ее бьет одна из ранее поставленных. Проигрывает тот, кто не может сделать ход. Кто из игроков может выиграть, как бы ни играл соперник?
Решение:
Приведем за Андрея стратегию, позволяющую ему победить. Первым ходом поставим ладью в центральную клетку доски, а дальше будем ходить симметрично относительно этой клетки. Покажем, почему у Андрея всегда есть ход согласно этой стратегии.
Пусть до некоторого момента Андрей мог ходить симметрично. Тогда перед ходом Бориса картинка была симметрична относительно центральной клетки. Если Андрей смог поставить ладью, то это значит, что и симметричная клетка до хода Бориса была свободна и непобита ладьей. Осталось заметить, что ладья не может бить ладью, симметричную себе относительно центра, если она не стоит в центральном столбце или центральной строке. Значит, Андрей сможет всегда сходить согласно своей стратегии.
Заметим при этом, что игра закончится не позже, чем через 121 ход, то есть когда все клетки будут заняты. Это значит, что кто-то все-таки проиграет. Мы доказали, что это не Андрей, значит, проиграет Борис.
Обратите еще раз внимание на последний абзац. На самом деле мы чаще всего доказываем, что согласно стратегии у игрока, за которого мы играем, всегда будет ход. Это означает, что он не проиграет. Чтобы доказать, что он все-таки выиграет, нужно еще объяснять, почему игра закончится.
Ответ:
Андрей
Задача 164. Игра в «Заполнение доски»-IX
Андрей и Борис играют на доске 100×100. Изначально все клетки доски белые. Каждым своим ходом Андрей красит в чёрный цвет одну или несколько белых клеток, стоящих подряд по диагонали. Каждым своим ходом Борис красит в черный цвет одну или несколько белых клеток, стоящих подряд по вертикали. (На рисунке справа показаны возможные первые ходы Андрея и Бориса на доске 4×4). Первый ход делает Андрей. Проигрывает тот, кто не может сделать ход. Кто выигрывает при правильной игре?
Решение:
Приведём одну из возможных выигрышных стратегий для Андрея. Он всё время будет делать ходы, параллельные одной из диагоналей доски (назовём её главной).
Первым ходом Андрей закрасит все клетки главной диагонали. После этого доска разбивается на две одинаковых “лесенки” (см. рис. 1). Мысленно сделаем каждую лесенку симметричной относительно вертикальной прямой, сдвинув в ней каждый горизонтальный ряд, кроме первого, на полклетки относительно предыдущего ряда (см. рис. 2).
В результате сдвигов и бывшие вертикали, и бывшие диагонали, параллельные главной, стали наклонными рядами. При этом “вертикали” одной лесенки симметричны “диагоналям” другой. Это значит, что на каждый ход Бориса Андрей может ответить симметричным ходом в другую лесенку (два таких ответа показаны на рис. 2).
Тогда после каждого хода Андрея ситуация на «сдвинутой» картинке будет оставаться симметричной, а значит, Андрей всегда сможет сходит согласно описанной стратегии. Так как игра закончится (не более чем за 104 ходов), в некоторый момент Борису будет некуда ходить, и Андрей выиграет.
Ответ:
Андрей
Задача 165. Игра в «Заполнение доски»-X
У Андрея и Бориса есть длинная шоколадка 15×100. Они по очереди выедают из неё квадратные куски любого размера (куски можно выедать только по линиям сетки). Начинает Борис. Проигрывает тот, кто не может сделать ход. Кто выигрывает при правильной игре?
Решение:
Пусть первым ходом Борис выедает квадрат 14×14 посередине шоколадки, чтобы вертикальная ось симметрии квадрата и ось симметрии прямоугольника совпадали. После этого хода ось симметрии прямоугольника делит остаток шоколадки на две одинаковые части. При этом никакой последующий ход не может пересечь ось симметрии, потому что куски должны быть квадратными.
Теперь на каждый ход Андрея Борис отвечает симметричным ходом. В итоге, Борис сделает последний ход в игре и победит.
Ответ:
Борис