Задача 201. Игра в «Заполнение доски»-XV
Андрей и Борис играют в игру на клетчатой доске 18×18. За один ход Андрей закрашивает одну клетку, а Борис — сразу две. Начинает Андрей. Проигрывает тот игрок, после хода которого какие-то шесть отмеченных клеток будут расположены в ряд по вертикали или горизонтали. Кто из игроков имеет выигрышную стратегию?
Решение:
Разобьем все клетки на тройки следующим образом: в каждой строке разбиваем их на тройки с номерами х, х+6, х+12. Играем за Бориса. Если Андрей ходит в некоторую тройку, то мы закрашиваем оставшиеся две клетки этой тройки.
Покажем, что тогда Борис никогда не проиграет. Пусть он не может сходить в соответствующую тройку. Тогда возможны два случая. Если после его хода образовывается вертикальный прямоугольник в одном из столбцов, то к этому момент уже был бы прямоугольник в столбце, в который Андрей сделал последний ход, то есть такое невозможно. Если же будет образовываться горизонтальный прямоугольник, то все его клетки будут из разных троек, но тогда клетка, в которую до этого сходил Андрей, также будет лежать в горизонтальном прямоугольнике, состоящем из клеток тех же троек.
Ответ:
Булат.
Задача 202. Игра в «Заполнение доски»-XVI
Дан куб, каждая грань которого — это клетчатое поле размером 2015 на 2015 клеток. В центре одной из граней стоит пешка. Андрей и Борис передвигают пешку по клеткам куба. Андрей может ходить только на соседнюю по стороне клетку (разрешается переходить на другую грань, если клетки соседние по стороне), а Борис может поставить пешку в любую клетку. Пешка красит за собой клетки. На закрашенную клетку пешку двигать нельзя. Изначальная клетка (центр грани) закрашена. Андрей ходит первым. Проигрывает тот, кто не может сделать ход. Кто выиграет при правильной игре обоих?
Решение:
Приведём выигрышную стратегию для Андрея. Число клеток на поверхности чётно (равно 2015×2015×6). Разобьём всю поверхность куба на доминошки; доминошки не пересекаются и покрывают весь куб. Легко видеть, что такие примеры есть. В начале хода Андрея пешка стоит в какой-то доминошке. Андрей ходит во вторую клетку доминошки. Если Андрей до этого действовал в соответствии с этой стратегией, то вторая клетка доминошки не закрашена, и сделать в неё ход можно. Очевидно, что последний ход сделает Андрей — хотя бы потому, что он всегда может сделать ход.
Задача 203. Игра в «Заполнение доски»-XVII
На клетчатой плоскости нарисован прямоугольник 3×2021 все клетки которого покрашены в синий цвет. Андрей и Борис по очереди перекрашивают в красный цвет две необязательно соседние синие клетки, расположенные либо в одной строке, либо в одном столбце. Начинает Андрей. Игрок, который не может сделать ход, проигрывает. Кто из игроков может обеспечить себе выигрыш вне зависимости от игры соперника?
Подсказка 1
Глобально в этой задаче нужно придумать стратегию, которая использует какие-то простые ходы до тех пор, пока так можно. Как только становится нельзя, придумываются другие простые ходы и снова делаются до тех пор, пока есть возможность их делать.
Подсказка 2
Чтобы было проще придумывать стратегию, занумеруйте клетки в столбцах цифрами 1, 2, 3.
Решение:
Пронумеруем клетки в каждом столбце сверху вниз числами 1, 2, 3. Играем за первого игрока. Сначала перекрасим две клетки 1, 3 в произвольном столбце. Каждый ход будем делать по следующему правилу. Если второй игрок ходит в клетки с номерами 1,i в некотором столбце, то мы ходим в клетки с номерами 1, j для любого j в некотором другом столбце. Иначе после хода второго проверяем, есть ли столбцы, в которых перекрашены клетки 2, 3, а клетка 1 — пустая. В таких столбцах выбираем клетки с номерами 1. Мы выберем не больше 2 клеток, так как свои ходом второй игрок может создать не более двух таких столбцов. Далее, если мы выбрали меньше 2 клеток, то до 2 клеток дополним любыми синими клетками с номерами 1 и перекрасим их. Делам так, пока можем.
Предположим, что мы не можем сделать очередной ход по нашему правилу. Заметим, что до предыдущего хода второго игрока не меньше половины перекрашенных клеток имели номер 1. Тогда всего покрашено не более 2×2021+2 клетки. То есть игра еще не закончена, поскольку есть строка, в которой не перекрашены хотя бы 2 клетки. С другой стороны, до последнего хода второго игрока количество не перекрашенных клеток в первой строке было четно. Если мы не можем сделать ход 1, j то это значит, что до этого второй игрок сделал ход 1, i. Тогда столбцов с перекрашенными клетками 2, 3 не образовалось. То есть в первой строке осталась синяя клетка, ее можно перекрасить вместе с другой клеткой из ее столбца — противоречие. Если же мы не можем перекрасить две синие клетки из первой строки, то это означает, что первая строка полностью закрашена.
Далее будем ходить произвольно. Предположим, что в некоторый момент мы не можем сделать ход. Тогда в каждой строке осталось не более одной синей клетки, но при этом первая строка заполнена. Количество синих клеток всегда остается нечетным, причем в данный момент их не больше 2. Тогда ровно 1 клетка не перекрашена. А значит, всего было совершено ходов (2021×3-1)/2=3031, то есть последний ход сделали мы — противоречие.
Ответ:
Андрей.
Задача 204. Игра в «Числа»-XVI
Андрей и Борис по очереди заполняют клетки квадратной таблицы 6×6 целыми числами. Каждым ходом игроки ставят одно число в любую из пустых клеток. Первым ходит Андрей. Когда вся таблица заполнится, они подсчитывают суммы чисел, стоящих в строках и в столбцах — всего 12 сумм. Если хотя бы 6 из них окажутся одинаковыми, то выиграет Борис, иначе — Андрей. Может ли Борис всегда выигрывать?
Решение:
Разобьем доску на вертикальные доминошки. Будем на месте Бориса на очередном шаге в ту же доминошку, куда только что ходил Андрей, ставить число, противоположное числу Андрея. Тогда по окончании игры сумма в каждой доминошке будет равна 0, поэтому и в каждом столбике сумма будет равна 0, то есть хотя бы 6 сумм будут равны 0.
Ответ:
Да, может.
Задача 205. Игра в «Камешки»-XIV
Два игрока, Андрей и Борис, имея каждый по 74 камешка, решили сыграть в такую игру: они по очереди будут выкладывать на стол камешки, за один ход — одну, две или три, а выиграет тот, кто положит на стол сотый по счёту камешек. Начинает Андрей. Кто может выиграть в такой игре, независимо от того, как будет действовать соперник?
Решение:
Если бы количество камней было неограниченным, то Борис мог бы просто дополнять ходы Андрея до четырёх и победить после своего 25-го хода. Однако заметим, что если Андрей будет всегда выкладывать по одному камешку, то Борису придётся выкладывать по три, а значит ему не хватит камней. Таким образом понимаем, что Борису необходимо сэкономить камешки. Если первым ходом Андрей положит два или три камешка, то Борис положит два или один и далее ему хватит камешков для победы.
Пусть Андрей положил первым ходом один камешек, тогда Борис в ответ положит также один. Далее возможны три варианта развития событий:
1) Если Андрей снова положил один камешек, то Борис также кладёт один, а далее дополняет до четырёх.
2) Если вторым ходом Андрей положит два камешка, то всего на столе будет четыре. Далее Борис положит один. Андрей не должен допустить, чтобы после хода Бориса количество камней делилось на 4, поэтому он будет выкладывать три Камешка. Далее всегда Борис будет выкладывать один камешек, вынуждая Андрея выкладывать три, но Андрей не сможет выложить сотый, так как ему не хватит камешков.
3) Если вторым ходом Андрей выложит три камешка, то Борис также ответит тремя, а далее будет дополнять.
Ответ:
Борис.
Задача 206. Игра в «Перемещение фишки»-II
Борис ставит короля на шахматную доску 8×8 после чего они с Андреем начинают играть в следующую игру. Каждый игрок своим ходом должен передвинуть короля по правилам шахмат (на соседнюю по стороне или диагонали клетку). Нельзя наступать на те клетки, в которых король бывал ранее. Начинает Андрей, ходы делают по очереди, проигрывает тот, кто не может сделать ход. Кто из игроков может победить, как бы ни играл соперник?
Подсказка 1
Так-с, симметрию тут не применишь... Тогда будем пытаться дополнить ход противника. Но до чего дополнять ходы противника на шахматной доске? Чтобы такое придумать, чтобы это дополнить?)
Подсказка 2
Вот если получится разбить клетки доски как-нибудь на пары соседних, то можно дополнять ход противника ходом в парную клетку.
Подсказка 3
Давайте разобьем доску на доминошки 2×1. Дело осталось за малым - определить победителя, который сможет применить стратегию дополнения)
Решение:
Разобьем клетки доски на пары-доминошки следующим образом:
Пусть Андрей своим ходом переставляет короля из текущей клетки в парную ей. Заметим, что Андрей всегда сможет так сходить, потому что после его хода во всех доминошках король побывал или на обеих клетках, или ни на одной. Тогда Борис может переставить короля только в доминошку, где обе клетки не посещены. В итоге, Андрей сделает последний ход и победит в игре.
Ответ:
Андрей.
Задача 207. Игра в «Камешки»-XV
На столе лежит 2025 камней. Андрей и Борис играют в игру по следующим правилам. Ходят по очереди, начинает Андрей. За один ход можно взять со стола 1 или 2 камня, но один и тот же игрок два раза подряд не может брать 2 камня. Проигрывает не имеющий хода. Кто из игроков сможет обеспечить себе победу вне зависимости от игры противника?
Подсказка 1
Один и тот же игрок два раза подряд не может брать 2 камня. Если бы не было этого ограничения, то можно было применить стандартную стратегию: дополнение хода противника (до 3 камушков). Можно ли как-то изловчиться и свести задачу к дополнению ходов противника?
Подсказка 2
Обойти ограничение можно - давайте смотреть не 1 ход игрока, а сразу 2 хода. С учетом запрета суммарно за 2 своих хода игрок может убрать либо 2, либо 3 камня. Как теперь придумать стратегию за одного из игроков?
Подсказка 3
Если у Андрей получится первыми 2 ходами сделать 2021 камней в кучке, то дальше ему достаточно дополнять за 2 своих хода 2 хода Бориса до 5 камней. Подумайте над тем, как Андрею правильно сделать первые 2 хода, а также, как делать последующие ходы, чтобы случайно не нарушить правило (про два подряд хода в 2 камня).
Решение:
Опишем выигрышную стратегию Андрея. Первым ходом он возьмет 1 камень. Это не наложит ограничений на его второй ход, поэтому он сможет дополнить ход Бориса так, чтобы после этого осталось 2021 камней.
Дальше Андрей будет действовать так, чтобы за две пары ходов было взято ровно 5 камней. Борис своими двумя ходами сможет в сумме взять 2 или 3 камня, поэтому Андрей сначала возьмет 1 камень (это не наложит ограничений на его второй ход), а потом, когда уже будет знать, что сделал Вася, дополнит его ход до 5 в сумме. При разборе каждой пятерки камней последний ход остается за Андреем. Поэтому, в частности, он возьмет последний камень и выиграет.
Ответ:
Андрей.
Задача 208. Игра в «Числа»-XVII
На доске написаны числа 1, 2, …, 100. За ход можно стереть 4 числа, сумма которых делится на 101. Андрей и Борис ходят по очереди, первый ходит Андрей. Проигрывает тот, кто не может сделать хода. Кто из игроков может выиграть, как бы ни играл соперник?
Решение:
Андрей разбивает все числа на 50 пар с суммой 101. Первым ходом он берет любые две пары целиком. Остается 48 пар. Вообще, после хода Андрея будут оставаться только целые пары, причем их количество кратно 4. Борис может взять либо две целые пары, либо одну целую пару и два числа из разных пар, либо по числу из 4 пар. В ответ Андрей берет все числа из начатых пар и столько же целых пар, сколько Борис. В результате пары ходов Бориса и Андрея они возьмут вместе ровно 4 пары, то есть 404 в сумме. Поскольку 404 и сумма Бориса кратны 101, то и сумма Андрея тоже, а число оставшихся пар уменьшилось на 4. Поэтому последний ход сделает Андрей и выиграет.
Ответ:
Андрей.
Задача 209. Игра в «Камешки»-XVI
На столе лежат N кучек по одному ореху в каждой (N>2). Двое ходят по очереди. За ход нужно выбрать две кучки, где числа орехов взаимно просты, и объединить эти кучки в одну. Выиграет тот, кто сделает последний ход. Для каждого N выясните, кто из играющих может всегда выигрывать, как бы ни играл его противник.
Решение:
Для выигрыша ему достаточно до самого конца объединять имеющиеся кучки так, чтобы была одна большая кучка и несколько кучек по одному ореху. При такой стратегии сохраняется инвариант — нечетность максимальной кучки после хода второго. В случае нечётного N второй придерживается такой стратегии до конца, а в случае чётного — до позиции из четырёх кучек N-3,1,1 и 1 после чего на любой ход первого: N-2,1,1 или N-3,2,1 — отвечает ходом N-2,2.
Ответ:
Всегда выигрывает второй.
Задача 210. Игра в «Числа»-XVIII
Андрей и Борис играют в игру. Они по очереди (начинает Андрей) выписывают по одной цифре, пока не получится шестизначное число. При этом первая выписанная цифра ненулевая и все выписанные цифры различны. Андрей выигрывает, если полученное шестизначное число делится хотя бы на одно из чисел: 2, 3 или 5. Если этого не случается, то выигрывает Борис. Кто выигрывает при правильной игре?
Подсказка 1
Подумаем, какие цифры и на какой позиции могли бы принести Борису победу? Что нужно сделать Андрею, чтобы предотвратить это?
Подсказка 2
Если на третий ход Бориса оставить ему числа 0, 2, 4, 5, 6, 8, то он проиграет. Значит, если Борис хочет победить, то в свой последний ход он подставит одно из чисел 1, 3, 7, 9. Какие еще вынужденные ходы можно приписать Борису?
Подсказка 3
Заметим, что чисел 1, 3, 7, 9 не так уж и много, значит Борис не должен их «закончить» раньше своего третьего хода. Тогда какие цифры он должен ставить в своих ходы?
Подсказка 4
Выходит, что Борис в свои первый и второй ходы должен ставить цифры из {0, 2, 4, 5, 6, 8}. Тогда какие цифры должен поставить Андрей, чтобы Борис не смог победить в конце?
Подсказка 5
Андрей своим первым и вторым ходом поставит 3 и 9. Осталось лишь разобрать случаи того, какие именно ходы сделает Борис! Подумайте, а как должен поступить Андрей вторым ходом, чтобы застать Бориса врасплох?
Подсказка 6
Обратите внимание на остатки чисел при делении на 3!
Решение:
Пусть a1b1a2b2a3b3 - итоговое шестизначное число. Пусть также A=0, 2, 4, 5, 6, 8 и B=1, 3, 7, 9. Заметим, что если Борис своим третьим ходом поставит цифру из множества A, Андрей выиграет, поскольку полученное число будет делиться на 2. Значит, b3 принадлежит множеству B.
Пусть Андрей первым ходом выберет цифру a1=3, а вторым ходом - цифру a2=9. Если Борис на первом или втором ходу выберет цифру из множества B, то своим третьим ходом Андрей заберет последнюю оставшуюся цифру из множества B, и Борис вынужден будет взять свою цифру b3 из A, что приведет к его проигрышу. Значит, Борис вынужден взять первые две свои цифры b1 и b2 взяты из множества A. Заметим, что Борис вынужден будет на последнем ходе выбрать либо цифру 1 , либо цифру 7 , которые дают одинаковый остаток 1 при делении на 3. Поэтому Андрею достаточно подобрать цифру a3 так, чтобы сумма цифр a1+b1+a2+b2+a3 давала бы остаток 2 при делении на 3. Поскольку a1=3 и a2=9 не влияют на остаток этой суммы, все зависит от остатка суммы b1+b2. Покажем, как действовать Андрею в каждом из случаев.
Если b1+b2 делится на 3, то Андрей выберет цифру a3 из набора (2,5,8): поскольку до этого момента эти цифры мог выбирать только Борис, как минимум одна из этих трех цифр останется не выбранной.
Если b1+b2 дает остаток 1 при делении на 3, Андрей выберет цифру a3=1. Как мы помним, Борис не мог ее выбрать на первых двух ходах.
Наконец, если b1+b2 дает остаток 2 при делении на 3, Андрей выберет цифру a3 из набора (0, 6). Борис не мог выбрать обе эти цифры, поскольку тогда b1+b2=6, а мы предположили, что b1+b2 дает остаток 2 при делении на 3 .
Таким образом, Андрей выиграет.
Ответ:
Андрей.
Задача 211. Игра в «Крестики-нолики»-II
Двое по очереди ставят крестики и нолики в клетки доски 9×9. Начинающий ставит крестики, его соперник — нолики. В конце подсчитывается, сколько имеется строчек и столбцов, в которых крестиков больше, чем ноликов — это очки, набранные первым игроком. Количество строчек и столбцов, где ноликов больше — очки второго. Тот из игроков, кто наберет больше очков, побеждает. Кто может победить, как бы ни играл соперник?
Решение:
Приведем выигрышную стратегию за первого игрока. Первым ходом он ставит крестик в центральную клетку. Затем после каждого хода второго игрока первый ставит крестик в центрально-симметричную клетку (аналогичный ход, симметричный ходу второго относительно центральной клетки). У первого всегда есть такой ход (центрально-симметричная клетка свободна после хода второго), так как всегда после хода первого доска симметрична сама себе относительно центральной клетки.
В конце получим также доску, симметричную самой себе относительно центральной клетки. То есть число столбцов, где крестиков больше, на 1 (центральный столбец) больше, чем столбцов, где ноликов больше. Аналогично строк, где больше крестиков, на 1 больше. Значит, первый победил.
Ответ:
Первый.
Задача 212. Игра в «Крестики-нолики»-III
На столе лежат 9 карточек с номерами от 1 до 9, каждый номер встречается по разу. Двое по очереди забирают себе по карточке со стола. Если в какой-то момент один из игроков собрал 3 карточки с суммой 15, то он победил. Иначе объявляется ничья. Есть ли у какого-нибудь из игроков выигрышная стратегия?
Решение:
Разместим все карточки в квадрате 3×3 как показано на рисунке (составляем так называемый магический квадрат). Заметим, что игрок выиграл тогда и только тогда, когда он первый забирает себе целый столбец, целую строку либо целую диагональ (сумма чисел на вертикалях, горизонталях и диагоналях магического квадрата постоянна, в нашем случае — 15). Будем отмечать карточки, которые забирает 1-ый игрок крестиками, а карточки второго — ноликами. Наша игра свелась в игру в крестики-нолики. Но, как известно, при правильной игре в крестики-нолики, ни у кого нет выигрышной стратегии.
Ответ:
Ни у кого.