Задача 213. Игра в «Камешки»-XVII
Два игрока по очереди выкладывают монеты в ряд. За один ход можно положить две или три монеты. Выигрывает тот, кто выложит 16 монету. Определите, какой игрок (первый или второй) обладает стратегией, которая позволит ему выиграть вне зависимости от ходов другого игрока. Опишите эту стратегию.
Подсказка 1
По условию двое игроков у нас выкладывают по 2 или 3 монеты. Но тогда за два хода суммарно какое число монет удобно выложить? Попробуйте перебрать хорошо известные стратегии.
Подсказка 2
Верно, мы сможем всегда дополнять количество до 5, то есть за два хода выкладывать 5 монет. Но теперь нужно понять, кому это выгодно. Учитывая, что первый может создать благоприятную ситуацию для себя, то, наверное, ему и будет полезно в дальнейшем дополнение. Но какой же первый ход ему нужно сделать?
Подсказка 3
Да, он может выложить, например, две монеты. А дальше он будет просто дополнять количество до пяти. Нужно только проверить концовку и убедиться, что первый выигрывает таким образом. Победа!
Решение:
Пусть первый игрок своим первым ходом положит 2 монеты, а следующими ходами класть столько монет, чтобы сумма его монет и монет, положенных перед этим вторым игроком была равна 5. В этом случае после третьего хода первого игрока в ряду будут лежать 12 монет. Далее, как бы не сходил второй игрок своим третьим ходом и как бы после этого не сходил первый игрок 16 монета будет положена первым игроком.
Ответ:
Первый игрок.
Задача 214. Игра в «Перемещение фишки»-III
По кругу расположены 16 луночек, одна из которых отмечена. Андрей и Борис играют в следующую игру. В начале игры Борис кладет шарик в одну из луночек. Далее за каждый ход Андрей называет натуральные число k (числа k могут отличаться на разных ходах), а Борис перемещает шарик из луночки, в которой он находится, на k луночек по часовой либо против часовой стрелки на свой выбор. Сможет ли Андрей играть так, чтобы через несколько ходов шарик гарантированно попал в отмеченную луночку?
Решение:
Приведём стратегию. Занумеруем луночки по часовой стрелке числами от 0 до n-1 так, что номер 0 имеет отмеченная луночка. Если шарик находится в луночке номер s он называет число s. Если Борис сдвинет шарик против часовой стрелки, то он немедленно попадет в отмеченную луночку. Значит, он вынужден сдвинуть шарик по часовой стрелке, то есть в луночку номер t, где t=2s (mod16). Так как t-2s делится на 16, то t - четно. Таким образом, после первого шага шарик обязательно находится в луночке с четным номером. Аналогично, на следующем шаге номер луночки будет обязательно делиться на 4 и так далее. Поэтому не позже чем на 4-м шаге номер луночки будет делиться на 16, а такая луночка только одна — отмеченная.
Ответ:
Да, сможет.
Задача 215. Игра в «Камешки»-XVIII
На столе есть две кучки камней, в которых соответственно 100 и 101 камень. Двое играют в игру, делая ходы по очереди. За ход разрешается взять кучку, убрать из неё какое-то количество камней (хотя бы один) и разбить оставшиеся в этой кучке камни на две непустые кучки. Проигрывает тот, кто не может сделать ход. Кто выиграет при правильной игре: тот, кто делает первый ход, или его соперник?
Решение:
Пусть первого игрока зовут Андреем, а второго — Борисом. Первым ходом Андрей уберет из кучки 101 один камень, а оставшиеся разделит на кучки из 1 (про которую можно забыть) и 99 камней. Теперь докажем более общий факт: если на столе лежат кучки из 2k и 2k-1 камней, то проигрывает тот, чья очередь ходить.
Пусть соперник Андрея Борис сделал ответный ход в кучку 2k-1 или разделил кучку 2k на две, взяв из нее больше одного камня. У него получились кучки из a и b камней, где a+b<2k-2. Тогда Андрей следующим ходом создает две такие же кучки, получает позицию a, a, b, b и выигрывает, делая ходы, симметричные ходам первого.
Пусть Борис возьмет один камень из кучки 2k и разделит ее на кучки из a и b камней. Тогда числа a и b будут разной четности. Пусть a четно. Тогда Андрей из кучки в 2k-1 камней получит кучки из a-1 и b камней (что возможно, так как a>2 после чего мысленно разделяет игру на две: одну на паре равных кучек b,b где он побеждает, делая ходы, симметричные ходам первого, и вторую — на паре кучек a, a-1 где он снова применяет стратегию, описанную выше.
Таким образом, у второго всегда есть возможность сделать ход, и он побеждает в силу того, что всего в игре можно сделать не больше 200 ходов.
Ответ:
Тот, кто делает первый ход.
Задача 216. Игра в «Числа»-XIX
Андрей и Борис играют в игру. У них есть карточки с цифрами от 1 до 8. Они по очереди берут по одной карточке, создавая себе по четырёхзначному числу: вначале они берут разряды тысяч, потом сотен, потом десятков, потом единиц (именно в таком порядке). Начинает Андрей. Если сумма получившихся чисел не делится на 6, то побеждает Андрей, а если делится — то Борис. Кто выигрывает при правильной игре?
Решение:
Если Андрей берет нечетную цифру, то мы берем нечетную, если Андрей берет четную цифру, то мы берем четную. Тогда заметим, что последние взятые цифры будут одной четности, откуда сумма двух чисел будет делиться на 2. Также она будет делиться на 3, так сумма цифр двух чисел равна 36 — делится на 3 (сумма цифр числа дает тот же остаток при делении на 3, что и само число). Поэтому сумма поделится на 6. А значит Борис выиграет.
Ответ:
Борис.
Задача 217. Игра в «Камешки»-XIX
Есть 3 кучи: 100, 101 и 2020 камней. Андрей и Борис играют в игру, по очереди удаляя по одному камню из двух разных куч. Игрок, который не может сделать ход, проигрывает. Начинает Андрей. У кого из игроков есть выигрышная стратегия?
Решение:
Первым ходов возьмем по 1 камню из куч 101 и 2020. Далее просто повторяем ходы Бориса. Заметим, что за каждую пару ходов, вес большой кучи уменьшается не более чем на 2, в то же время суммарный вес двух маленьких куч уменьшается хотя бы на 2. Тогда понятно, что мы всегда сможем сделать ход, так как в маленьких кучах, в которые сходил Борис, будет нечетное число камней, а в большой куче будет больше камней, чем в двух других кучках в сумме. Поэтому рано или поздно мы придем в ситуацию, когда обе маленькие кучки станут нулями. Тогда в этот момент Борис не сможет сделать ход.
Ответ:
У Андрея.
Задача 218. Игра в «Камешки»-XX
Два игрока играют в игру: они по очереди вытаскивают камни из кучки, в которой изначально было n камней. В свой первый ход первый игрок берет из кучи один или несколько камней, но не может забрать все камни. Каждым следующим ходом очередной игрок должен забрать из кучи количество камней, являющееся делителем числа камней, забранного противником на предыдущем ходу, и не превосходящее числа камней в куче. Выигрывает тот, кто заберет последний камень. Для каждого n>1 определите, у кого из соперников есть выигрышная стратегия.
Решение:
Заметим, что если в куче нечетное число камней, то первый игрок гарантирует себе победу, взяв на первом ходу 1 камень: тогда каждым следующим ходом игроки будут забирать по одному камню, и последний камень заберет первый игрок. Когда n чётно, тот, кто первым сделает нечетный шаг, проиграет: такой шаг был сделан из четного числа — значит, он не будет последним, а противник заберет один камень, что и обеспечит ему победу.
Если n=2, то второй игрок, очевидно, побеждает. Если n=3, то побеждает первый игрок, забирая первым ходом 1 камень. Если n=4, то побеждает второй игрок: если первый берет 1 камень, то второй возьмет последний камень, а если первый игрок первым ходом берет 2 или 3 камня, то второй игрок первым своим ходом забирает остальные камни.
Докажем по индукции, что для всех четных n от 2^(k-1) до 2^k-1 (для натурального k≥2 ) побеждает первый игрок, а для n=2k — второй. База индукции (k=2) разобрана выше.
Пусть 2k-1+1≤n≤2k-1 для натурального k≥3. Тогда первый игрок сводит игру к таковой с n/2 камнями (т.е. берет вдвое больше камней, чем взял бы в игре с n/2 камнями), где у него есть победная стратегия согласно предположению индукции, поскольку 2k-2+1≤n/2≤2k-1-1. Единственный способ помешать ему — взять нечетное число камней, но, как показано выше, тот, кто первым возьмет нечетное число камней, проигрывает.
Пусть теперь n=2k для k≥3. Тогда уже второй игрок применяет стратегию "половинчатой" игры, т.е. берет в 2 раза больше камней, чем взял бы в игре с n/2 камнями. Согласно предположению индукции, это обеспечит ему победу.
Ответ:
При n=2k второй игрок может гарантировать себе победу. При прочих n>1 выигрышная стратегия есть у первого игрока.
Задача 219. Игра в «Распределение»-I
Андрей и Борис играют в игру. Изначально пять одинаковых пустых вёдер ёмкостью a стоят по кругу. За ход Андрей берёт изо рва литр воды и распределяет его по вёдрам как ему заблагорассудится, а затем Борис опустошает любые два соседних ведра. Андрей выигрывает, если после какого-то его хода хотя бы одно из вёдер переполнится. При каких a Борис может не допустить этого?
Подсказка 1
Попробуйте поиграть за Андрея. Выработайте какую-нибудь стратегию, из нее подумайте о действиях Бориса.
Подсказка 2
Ответ а≥2. При меньших Андрей может в первое ведро наливать почти все, а остальное по капельке сливать в третье ведро. Поймите, почему это не работает при больших а.
Подсказка 3
Реализуйте за Бориса "жадный" алгоритм, сливая из наибольшей по объему пары вёдер.
Решение:
Сначала покажем, что при емкости вёдер a<2 Андрей сможет добиться того, что ведро будет переполнено. Если a<1, то Андрею достаточно 1 литр поместить в одно какое-то ведро.
Иначе пусть a=2-x, где 0<x<1 и пусть ведра пронумерованы по кругу: 1, 2, 3, 4, 5 соответственно. Тогда пусть Андрей наливает в первое ведро 1-x/2, а в третье x/2 литров воды.
Борис может опустошить только одно из ведер: либо первое, либо третье, потому что они не стоят рядом. Дальше будет действовать следующим образом: если Борис не опустошает первое ведро, то пусть Андрей просто дольет в первое ведро 1 литр и в нем станет 2-x/2>a, поэтому это ведро переполнится. Иначе Борис опустошил первое ведро, но тогда третье ведро осталось заполненным. Пусть Андрей также наливает в первое ведро 1-x/2, а в третье x/2 литров воды до того момента, когда либо Борис не опустошает первое ведро (тогда Андрей доливает в первое ведро 1 литр и побеждает), либо в третьем ведре станет n*x/2>a, где n — число раз, когда Борис не опустошала третье ведро.
Теперь покажем, что при a>2 Борис может не допустить переполнений. Будем играть за Бориса. Всегда будем выбирать такие 2 соседних ведра, в которых суммарно наибольшее число воды. Причем, если в нескольких парах ведер суммарно поровну воды, то, действуем, как угодно. Тогда мы будем каждым ходом опустошать хотя бы 2/5 суммарного объема. Заметим, что тогда после опустошения будет всегда оставаться менее 1.5 литров воды суммарно во всех ведрах. Тогда объем любого ведра меньше (3/2+1)*2/5=1. Получается, долив 1 литр, Андрей получит ведро объемом меньше двух литров.
Ответ:
При a>2.
Задача 220. Игра в «Заполнение доски»-XVIII
Дана клетчатая полоска 1×2021. Андрей и Борис пишут по очереди в ней буквы, начинает Андрей. Андрей может писать только букву «А», Борис — только букву «Б». Борис очень хочет, чтобы после заполнения всей полоски буквами в каких-то трёх последовательных клетках можно было прочитать “АБА”. Сможет ли Андрей ему помешать?
Решение:
После первого хода Андрея хотя бы с одной стороны от клетки, в которой стоит буква «А» есть две свободные. Поставим «Б» рядом с «А» с соответствующей стороны. Далее ходим куда угодно, кроме второй свободной клетки. Заметим, что кроме трёх выбранных клеток, на полоске осталось 2018 свободных клеток. Поэтому, если Андрей тоже никогда не ходит в незанятую вторую клетку, то мы по очереди заполняем оставшиеся 2018 клеток. Но их четное число, так что рано или поздно Андрею всё-таки придётся сходить в третью выбранную клетку.
Ответ:
Нет, не сможет.
Задача 221. Игра в «Крестики-нолики»-IV
Двое играют в крестики-нолики на бесконечной клетчатой бумаге по таким правилам: первый ставит два крестика, второй — нолик, первый — снова два крестика, второй — нолик и т.д. Первый выигрывает, когда на одной вертикали или горизонтали стоит рядом 100 крестиков. Докажите, что первый всегда может добиться победы.
Решение:
Поставим 2^100 крестиков на одной вертикальной линии на огромном расстоянии друг от друга. За эти ходы второй игрок испортит не более половины крестиков (то есть поставит рядом с ними нолик). В соседнюю клетку справа от 2^99 неиспорченных крестиков поставим ещё по крестику. За эти ходы второй испортит не более 2^98 пар крестиков. В соседнюю клетку справа от неиспорченных 2^98 пар крестиков поставим по крестику. За эти ходы второй испортит не более 2^97 троек и так дальше. В скором времени мы получим хотя бы две полоски из 99 крестиков. Далее первый припишет к одной из них справа крестик и победит.
Задача 222. Игра в «Камешки»-XXI
Андрей и Борис играют в такую игру: по очереди обрывают лепестки у ромашки с 64 лепестками. За один ход разрешается сорвать любое нечётное количество лепестков, меньшее 16, причем запрещается повторять уже сделанные ходы. Например, если Борис при своём ходе сорвёт 3 лепестка, то в дальнейшем ни Андрей, ни Борис сорвать 3 лепестка не имеют права. Выигрывает тот игрок, который сорвёт последний лепесток. Начинает Андрей. Кто из них может выиграть, как бы ни играл соперник?
Решение:
Заметим, что 1+3+5+…+15=64. С учётом того, что ходы не могут повторяться, всего будет сделано 8 ходов, как бы ни играли Андрей и Борис. Следовательно, выигрывает игрок, который делает ходы с чётным номером, то есть Борис.
Ответ:
Борис.
Задача 223. Игра в «Числа»-XX
На доске написано число 2. Двое играют в игру, делая ходы по очереди: каждый из игроков своим ходом может написать на доске любую степень двойки (то есть число вида 2k). Игрок, после хода которого на доске появятся две одинаковые цифры, проигрывает. У кого из игроков (у того, кто начинает, или у его соперника) есть способ выиграть при любой игре другого? Как он должен действовать?
Решение:
Тот, кто начинает, может написать число 2^14=16384 и победить, потому что любая степень двойки оканчивается на цифры 2, 4, 6, 8, а все эти цифры уже будут написаны на доске.
Ответ:
У ходящего первым игрока. Он может написать число 16384.