Задача 234. Игра в «Камешки»-XXIII
Есть две коробки, в одной 2017 конфет, а в другой 2018. Играют двое, ходят по очереди. За один ход каждый может съесть любое количество конфет, отличное от нуля, из любой коробки. Правила игры не допускают, чтобы после какого-то хода число конфет в одной из коробок делилось на число конфет в другой. Проигрывает тот, кто не может сделать ход, не нарушив этого условия. Кто сможет выиграть: начинающий игру или второй игрок, как бы ни играл его соперник?
Решение:
Для того, чтобы выиграть, первый игрок после каждого своего хода должен создавать ситуацию, когда в одной из коробок 2n конфет, а в другой 2n+1 (n — натуральное число). В такой ситуации он заведомо не проигрывает.
Сначала он съедает две конфеты из второй коробки и получает нужную ситуацию. В дальнейшем, в ответ на любой ход второго игрока первый будет восстанавливать такое распределение конфет. Покажем, что он сможет это делать. Возможны 4 случая:
1) Второй ест четное количество конфет из той коробки, где их 2n. Тогда в ней останется 2m конфет (m>0, иначе второй проиграл). В ответ первый съедает из другой коробки такое же количество конфет, и в ней остается 2m+1.
2) Второй ест нечетное количество конфет из той коробки, где их 2n. Тогда в ней останется 2m+1 конфет (m>0, иначе второй проиграл). В ответ первый съедает из другой коробки на две конфеты больше и в ней остается 2m+1.
3) Второй ест нечетное количество конфет из той коробки, где их 2n+1. Тогда в ней останется 2m+1 конфет, где 0<m<n (иначе второй проиграл). В ответ первый съедает из другой коробки на две конфеты меньше и в ней остается 2m+1.
4) Второй ест четное количество конфет из той коробки, где их 2n+1. Тогда в ней останется 2m+1 конфет (m>0, иначе второй проиграл). В ответ первый съедает из другой коробки такое же количество конфет, и в ней остается 2m.
Действуя таким образом, первый (если второй до этого ни разу не ошибётся) сведет игру к тому, что в одной коробке останется две конфеты, а в другой три, и после этого второй проигрывает, какой бы ход он ни сделал.
Ответ:
Первый игрок.
Задача 235. Игра в «Камешки»-XXIV
Имеется 5 кучек по 2018 камней в каждой. Двое по очереди убирают по одному камню из какой-нибудь кучки до тех пор, пока в кучках есть камни. Первый выигрывает, если в какой-то момент времени найдется четыре кучки с разным количеством камней. Иначе выигрывает второй. Кто из игроков может победить, как бы ни играл соперник?
Решение:
Пусть первый берет из первой кучки, пока там не останется 2018-1000 камней. Упорядочим по возрастанию остальные кучки, и забудем про вторую кучку. Будем брать из третьей кучки, пока не возьмем оттуда (возможно вместе со вторым игроком) еще 250 камней. Упорядочим две оставшиеся кучки. Покажем, что первый или уже выиграл, или выиграет своим следующим ходом.
После того, как игроки взяли 1000 камней из первой кучки и упорядочили, разность между первой и третьей стала не менее 500, после чего из этих кучек второй может взять не более 250 камней. Аналогично, после того как игроки взяли 250 камней из третьей кучки и упорядочили, разница между третьей и пятой стала хотя бы 125. Тогда в первой, третьей и пятой кучках разница в количестве камней больше 120. И следующим ходом первый (при необходимости) берет камень из второй кучки и выигрывает.
Ответ:
Первый игрок.
Задача 236. Игра в «Деление»- I
В начале игры у Малыша и Карлсона есть один кусок шоколадки в виде квадрата 2025×2025 клеточек. Каждым ходом Малыш делит какой-нибудь кусок по клеточкам на три прямоугольных куска, а Карлсон съедает один из этих трёх кусков по своему выбору. Игра заканчивается, когда сделать очередной ход невозможно. Если всего было сделано чётное число ходов — побеждает Малыш, если нечётное — Карлсон. Кто выигрывает при правильной игре?
Решение:
Назовем кусок шоколадки большим, если его можно разрезать, и малым, если нельзя. Изначально есть только один большой кусок, а в конце игры их 0. Карлсон может играть так, чтобы четность количества больших кусков после его хода обязательно менялась: один большой кусок уничтожается ходом Малыша, после чего появляется от 0 до 3 новых больших кусков. Если количество новых больших кусков нечетно, то один точно есть и Карлсон его съест. Если же количество больших кусков четно, то есть хотя бы один малый и Карлсон съест именно малый кусок. Итак, число больших кусков после каждой пары полуходов меняет четность, а по окончании игры чётность чисел больших кусков должна измениться, значит, будет сделано нечётное количество ходов, т.е. Карлсон выиграет.
Ответ:
Карлсон.
Задача 237. Игра в «Распределение»-II
По краю круглого стола стоят n пустых стаканов n≥3. Андрей и Борис по очереди (начиная с Андрея) наливают в них квас. Андрей в свой ход наливает квас в выбранный им пустой стакан, у которого оба соседних с ним стакана либо пустые, либо полные. Борис в свой ход наливает квас в выбранный им пустой стакан, у которого один соседний с ним стакан пустой, другой — полный. Проигрывает игрок, не имеющий хода. При каких n Андрей выигрывает вне зависимости от действий Бориса?
Решение:
Если стакана 3, то побеждает Андрей за один ход. Если 4, то Борис ставит стакан рядом с Петей и сам побеждает за один ход, пусть далее n>4.
Назовём “закваской” набор из подряд идущих заполненных стаканов. Тогда Борис может увеличить размер закваски, но не может добавить новую. В то же время Петя может либо объединить две закваски, либо создать новую из одной кружки. Первым ходом Андрей заполняет произвольную кружку, получая одну закваску. Назовём “застольем” набор идущих подряд по кругу заквасок. Далее пусть каждым своим ходом Андрей добавляет новую закваску, пропуская один стакан после текущего конца застолья, то есть после последней закваски в нём. Пусть Андрей спустя k добавленных Петей заквасок не может сделать ход. Тогда всего на столе 2k полных стаканов и не более k+1 пустых (по одному между заквасками и максимум два после конца застолья). То есть 3k+1≥n>4 или k≥2. То есть найдётся хотя бы одно междузаквасье длиной один, где Андрей может заполнить стакан, а Борис нет (заквасок хотя бы 2). Если после застолья идёт один пустой стакан, то Борис не может сделать ход и уже проиграл (если 0 аналогично), иначе их два. Борис заполнит один из них и второй следующим ходом сможет заполнить Андрей, то есть у него есть уже два дополнительных хода, а у Бориса их не осталось, потому на следующем ходу он проиграет.
Ответ:
при n=3 и при n≥5.
Задача 238. Игра в «Камешки»-XXV
Изначально на столе лежат три кучки из 100,101 и 102 камней соответственно. Андрей и Борис играют в следующую игру. За один ход каждый из них может взять себе один камень из любой кучи, кроме той, из которой он брал камень на своем предыдущем ходе (на своём первом ходе каждый игрок может брать камень из любой кучки). Ходы игроки делают по очереди, начинает Андрей. Проигрывает тот, кто не может сделать ход. Кто из игроков может выиграть, как бы ни играл соперник?
Решение:
Пусть Андрей возьмет камень из кучки 101. Тогда если Борис возьмет камень из другой кучи, то Андрей сможет просто брать камень с той же кучи, что и Борис. Почему? Если у Бориса был ход (рассматриваем уже хотя бы второй ход Бориса, так как с первыми ходами все работает), значит, на своем предыдущем ходе Борис брал камень из другой кучи, но Андрей брал камень из той же кучи, поэтому сейчас он тоже может взять камень, откуда его взял Борис. Таким образом, в этом случае после хода Андрея во всех трех кучках камней четно, а значит, Борис проиграет.
Если же Борис своим первым ходом взял камень тоже из второй кучи, то Андрей уже не может повторить за ним ход, так как он только что взял из этой кучи камень. Пусть тогда Андрей делает вот что: если Борис берет камень из второй кучи, то он берет из первой, если Борис берет из первой кучи, то он берет из второй, если Борис берет из третьей кучи, то он берет тоже из третьей кучи.
Почему у Андрея всегда есть ход? Если Борис берет камень из третьей кучи, то на предыдущем ходу он брал камень из первой или второй кучи, а значит, и Андрей тоже, поэтому, Андрей может взять камень из третьей кучи (еще важно, что в третьей куче после хода Бориса камней всегда нечетно, поэтому они там не могли закончиться после его хода). Если же Борис берет камень из первой кучи, то Андрею нужно взять камень из второй, но если бы он не мог, то это бы означало, что первый своим предыдущим ходом брал камень из первой кучи, противоречие, значит, Андрей может взять камень из второй кучи, причем, после его хода камней в первой и второй куче равное количество, а значит, камни во второй кучи есть. Аналогично, если Борис взял камень из второй кучи.
Таким образом, выигрывает Андрей.
Ответ:
Андрей.
Задача 239. Игра в «Буквы»-I
Андрей выписал все слова (не обязательно осмысленные), которые получаются вычеркиванием ровно двух букв из слова “ТРАНСФОРМИРОВАНИЕ”, а Борис сделал то же самое со словом “БЕЗРЕЗУЛЬТАТНОСТЬ”. У кого получилось больше слов?
Решение:
В обоих словах по 17 букв, но в слове Бориса при вычеркивании АТ и ТА получается одно и то же слово, а у Андрея повторяющихся слов нет, так как нет двух одинаковых букв подряд и двух одинаковых через одну.
Ответ:
У Андрея.
Задача 240. Игра в «Числа»-XXIII
Два игрока по очереди выписывают на доске в ряд слева направо произвольные цифры. Проигрывает игрок, после хода которого одна или несколько цифр, записанных подряд, образуют число, делящееся на 11. Кто из игроков победит при правильной игре?
Решение:
Обозначим цифры, выписываемые игроками, последовательно через a1, a2, a3,… , где цифры с нечётными номерами выписывает первый, а с чётными — второй. Рассмотрим остатки ri от деления на 11 знакопеременных сумм S0=0, S1=a1, S2=a1-a2, Sk=a1-a2+a3+…
Согласно признаку делимости на 11 после k-го хода на доске возникнет число, кратное 11 тогда и только тогда, когда Sk совпадает с одним из S0,…,S(k-1). Расположим эти остатки по кругу по часовой стрелке от 0 до 10 и изобразим последовательность ходов как процесс перемещения по кругу по неповторяющимся остаткам S. При этом первый игрок i-м ходом "прибавляет" к S(i-1) любое число ai от 1 до 9, а второй — любое число от (-1) до (-9). Таким образом, кроме повтора уже встречавшегося остатка, первому игроку запрещён ход против часовой стрелки на 1, а второму — ход по часовой стрелке на -1. После i-го хода свободными останутся 10-i остатков. Игрок гарантированно может сделать ход, если есть хотя бы два свободных остатка, значит, первые восемь ходов игроки сделать смогут, а 11-й ход сделать нельзя никогда.
Рассмотрим ситуацию после седьмого хода (это ход первого), когда свободны 3 остатка. Разберём три случая.
1) Свободные остатки расположены подряд: i-1, i, i+1. Тогда второй выписывает число с остатком i (занимает остаток i), первый — i+1, а второй i-1 и выигрывает.
2) Остатки расположены так: два рядом — i, i+1 и один отдельно — j. Тогда второй занимает один из остатков i, i+1, далее либо первый занимает остаток i+1, второй — j и выигрывает, либо первый занимает j, а второй — один из оставшихся i+1 и выигрывает.
3) Никакие два остатка не стоят рядом: i, j, k. Тогда второй может занять один из них и после хода первого, второй может занять последний свободный остаток и выиграть.
Ответ:
Второй игрок.
Задача 241. Игра в «Числа»-XXIV
Андрей и Борис играют в следующую игру. На доске написаны числа от 1 до 2014. За ход разрешается вычеркнуть любое число вместе со всеми его делителями. Ходят по очереди, начинает Андрей. Проигрывает тот, кто не может сделать ход. Кто выигрывает при правильной игре?
Решение:
По правилам игры ничьих не бывает, поэтому либо первый игрок, либо второй имеет выигрышную стратегию. Первый игрок может “передать ход” второму, вычеркнув первым ходом 1. Действительно, пусть второй вычёркивает число x и все его делители. После этого хода вычеркнуты те числа, какие были бы вычеркнуты, если бы первый игрок первым своим ходом вычеркнул x (и все его делители). Поэтому у второго игрока не может быть выигрышной стратегии: первый игрок, “передав ход”, может играть, следуя любой стратегии второго игрока. Значит, выигрышная стратегия есть у первого игрока.
Ответ:
Первый.
Задача 242. Игра в «Камешки»-XXVI
Даны две кучки спичек. В одной 2025, в другой 2026 спичек. Двое играют в следующую игру: при своем ходе каждый выбрасывает одну из двух кучек, а другую делит на две не обязательно равные кучки. Проигравшим считается тот, кто не может разделить кучку на две части. Кто может выиграть при правильной игре?
Решение:
Игра конечна, следовательно, у одного из игроков есть выигрышная стратегия. Докажем, что у второго не может быть выигрышной стратегии. Предположим, что она у него есть, и будем играть за первого. Первым ходом выбросим кучку 2025, а вторую разделим на 2025 и 1. Второй игрок обязательно выбросит кучку 1 и разделит как-то кучку 2025. С этого момента у второго игрока есть ответные ходы на каждый наш ход, соответствующие выигрышной стратегии. Тогда можем начать игру по-другому: первым ходом выбросим кучку 2026 и разделим кучку 2025, так же, как и второй игрок разделил бы ее в соответствии со своей выигрышной стратегией. Теперь будем отвечать на ходы второго по его же стратегии и победим. Значит, у первого тоже есть выигрышная стратегия. Противоречие.
Доказали, что первый игрок имеет выигрышную стратегию.
Ответ:
Первый.
Задача 243. Игра в «Карты»- I
У Андрея есть колода из 36 карт (4 масти по 9 карт в каждой). Он выбирает из неё половину карт, какие хочет, и отдает Борису, а вторую половину оставляет себе. Далее каждым ходом игроки по очереди открывают по одной карте по своему выбору (соперник видит масть и достоинство открытой карты), начиная с Андрея. Если в ответ на ход Андрея Борис смог положить карту той же масти или того же достоинства, то Борис зарабатывает одно очко. Какое наибольшее количество очков Борис может гарантированно заработать?
Решение:
Если Андрей возьмёт себе все черви, все тузы, всех королей и всех дам, то Борис не сможет набрать очки на тузе, короле и даме червей, т. е. наберёт не больше 15 очков.
Теперь докажем, что при любом выборе Андрея Борис может заработать не меньше 15 очков. Выложим карты в клетки таблицы 4×9 (в одном столбце карты одного достоинства, в одной строке — карты одной масти). Докажем, что если Андрей закрасил черным 18 клеток, то Борис может выделить не менее 15 непересекающихся xороших пар: в каждой паре две клетки разного цвета, находящиеся в одной строке или одном столбце. (Тогда Борис на ход одной картой из пары сможет отвечать ходом второй карты из этой пары и заработать 15 очков.)
Назовём типом столбца количество чёрных клеток в нём. Сначала Борис рассматривает столбцы типа 2 (если они есть). Каждый из них, очевидно, разбивается на две хорошие пары.
Далее Борис рассматривает пары столбцов типа 0 и 4. Каждая такая пара, очевидно, разбивается на четыре хорошие пары клеток.
Далее Борис рассматривает пары столбцов типа 1 и 3. Каждая такая пара тоже разбивается на четыре хорошие пары клеток (см. рисунок ниже).
Когда указанные пары столбцов закончатся, в силу симметрии можно считать, что “необработанными” останутся только столбцы типов 4 и 1. Если это a столбцов типа 4 и b столбцов типа 1, то 4a+b=3b, т. е. b=2a. В тройке из столбца типа 4 и двух столбцов типа 1 Василиса сможет выделить не менее пяти хороших пар клеток (см. рисунок справа).
Так как 3a=a+b≤9, то на всей доске останется не более трёх нехороших пар, т. е. Борис «потеряет» не больше 3 очков.
Ответ:
15.