Задача 244. Игра в «Камешки»-XXVII
В каждой из трёх коробок лежит по 2025 спичек. Двое играющих берут по очереди любое число спичек из любой коробки, но только из одной. Выигрывает тот, кто берёт последнюю спичку. Докажите, что тот, кто ходит первым, может выиграть, как бы ни играл его партнер.
Решение:
Первым ходом начинающий должен забрать все спички из любой коробки. После этого останутся две коробки, и ему надо в дальнейшем каждым своим ходом брать столько же спичек, сколько взял перед этим его партнер, но из другой коробки. Придерживаясь такой стратегии, первый будет каждым своим ходом уравнивать число спичек в коробках и ясно, он рано или поздно выиграет.
Задача 245. Игра в «Камешки»-XXVIII
Имеется кучка из 100 камней. Двое играют в следующую игру. Первый игрок забирает 1 камень, потом второй может забрать 1 или 2 камня, потом первый может забрать 1,2 или 3 камня, затем второй 1,2,3 или 4 камня, и так далее. Выигрывает тот, кто забирает последний камень. Кто может выиграть, как бы ни играл соперник?
Решение:
Докажем, что для любого натурального n≥10 первый игрок на своём n-ом ходе может добиться, чтобы количество забранных из кучки камней равнялось n2, и второй игрок не сможет ему помешать. Доказательство проведём индуктивно.
В свой первый ход первый игрок забирает один камень, т. е. число забранных камней равно 12. Пусть в свой n-й ход первому игроку удалось сделать так, чтобы количество забранных камней равнялось n2. В свой n-й ход второй игрок может взять от 1 до 2n камней. Поскольку (n+1)2-n2=2n+1 после его хода общее количество забранных камней будет больше n2 и меньше (n+1)2. Первый игрок в свой следующий ход может взять от 1 до 2n+1 камня и точно сможет получить (n+1)2 забранных камней независимо от предыдущего хода второго игрока.
Таким образом, поскольку 100=102, побеждает первый игрок: ему достаточно каждый раз забирать такое число камней, чтобы общее число забранных камней было точным квадратом, и на своём 10 ходе он возьмёт последний камень.
Ответ:
Первый.
Задача 246. Игра в «Карты»- II
Андрей и Борис разложили на столе 13 различных карт. Каждая карта может лежать в одном из двух положений: рубашкой вверх или рубашкой вниз. Игроки должны по очереди переворачивать по одной карте. Проигрывает тот игрок, после хода которого повторится какая-то из предыдущих ситуаций (включая изначальную). Первый ход сделал Борис. Кто сможет выиграть независимо от того, как будет играть соперник?
Решение:
Выигрышная стратегия Бориса состоит в том, чтобы каждый раз переворачивать одну и ту же карту (например, пиковую шестерку). Все возможные позиции можно разбить на пары, отличающиеся лишь расположением пиковой шестерки. Если в ответ на ход Бориса Андрей тоже перевернёт пиковую даму, то повторится предыдущая позиция, и он проиграет. Поэтому он вынужден переворачивать другую карту. А Борис, перевернув в ответ пиковую даму, получит позицию, парную к той, которая только что была. Таким образом, каждым ходом Андрею придётся “начинать” новую пару, и Борис всегда сможет сделать ответный ход, “закончив” пару. Так как количество возможных позиций конечно, то рано или поздно Андрей не сможет открыть новую пару и проиграет.
Ответ:
Борис.
Задача 247. Игра в «Числа»-XXV
На доске написано число 2. За ход разрешается прибавить к числу на доске любой из его делителей, меньший самого числа. Выигрывает тот, кто первым получит число больше 1000000. Кто может выиграть при правильной игре?
Решение:
Первый игрок напишет число 3, второй число 4. Далее первый может написать число 6, а может написать число 5 и тогда второй напишет число 6. После написания числа 6 выигрышная стратегия есть либо у ходящего, либо у его противника. Так как первый игрок после написания числа 6 может по своему желанию оказаться и ходящим, и противником ходящего, он может воспользоваться выигрышной стратегией. Таким образом мы доказали, что у первого есть выигрышная стратегия.
Ответ:
Первый.
Задача 248. Игра в «В слепую»-I
Странник хочет выйти из круглой комнаты с n дверями, n-1 из которых заперты на ключ. За одну попытку он может проверить любые три двери, расположенные подряд, и если одна из них не заперта, то он в неё выйдет. После каждой попытки Хранитель запирает дверь, которая была открыта, и отпирает одну из соседних дверей. Какую именно, Странник знает. Как ему действовать, чтобы наверняка выйти из комнаты?
Решение:
Занумеруем двери числами 1, 2, 3,…, n например, по часовой стрелке. Пусть он будет рассматривать двери с номерами 2k-1, 2k, 2k+1 для k=(1, 2, 3…).
Первой попыткой Странник проверяет двери 1, 2 и 3. Если после этого он не сумел выйти из комнаты, то двери 1, 2 и 3 были заперты. Дверь 2 останется запертой даже после того, как Хранитель запрёт открытую и отопрёт одну из соседних.
Второй попыткой Странник проверяет двери 3, 4 и 5. Если после этого он не сумел выйти из комнаты, то двери 3, 4, 5 были заперты, а с учетом того, что 2 тоже заперта, можно утверждать, что двери 3 и 4 останутся запертыми и после действий Хранителя.
Пусть на k шаге он открывает двери с номерами 2k+1, 2k+2, 2k+3. И пусть ему известно, что k-1 дверей с номерами (k+1), (k+2), …, 2k точно были закрыты перед его ходом. Тогда после проверки дверей Странником и действий Хранителя мы будем знать, что k дверей с номерами (k+2), (k+3), … (2k+2) точно заперты, потому что перед ходом Хранителя были заперты соседние к ним двери.
Тогда не более, чем за n шагов Странник будет знать все запертые двери и сможет выбрать открытую.
Задача 249. Игра в «Камешки»-XXIX
Два игрока по очереди выкладывают монеты в ряд. За один ход можно положить две или три монеты. Выигрывает тот, кто выложит 16 монету. Определите, какой игрок (первый или второй) обладает стратегией, которая позволит ему выиграть вне зависимости от ходов другого игрока. Опишите эту стратегию.
Решение:
Пусть первый игрок своим первым ходом положит 2 монеты, а следующими ходами класть столько монет, чтобы сумма его монет и монет, положенных перед этим вторым игроком была равна 5. В этом случае после третьего хода первого игрока в ряду будут лежать 12 монет. Далее, как бы не сходил второй игрок своим третьим ходом и как бы после этого не сходил первый игрок 16 монета будет положена первым игроком.
Ответ:
Первый игрок.
Задача 250. Игра в «Заполнение доски»-XXII
Двое играют в следующую игру на изначально полностью белой доске 8×8. Первый игрок своим ходом должен покрасить в чёрный цвет одну белую клетку, а второй игрок — пару белых клеток с общей стороной (доминошку). Проигрывает тот, кто не может сделать ход. Кто из игроков может победить, как бы ни играл соперник?
Решение:
Заметим, что пока не все клетки покрыты, у первого всегда есть ход. Клеток всего 64, а после ходов второго их количество кратно 3. Значит, у первого всегда будет ход и он победит. В качестве стратегии будем ходить в первую попавшуюся клетку.
Ответ:
Первый.
Задача 251. Игра в «Крестики-нолики»-V
Двое игроков ставят крестики и нолики в клетки доски 10×10 (первый — крестики, второй — нолики). Запрещено ставить крестик и нолик в соседние клетки, а также ставить рядом два нолика. Проигрывает тот, кто не может сделать ход. Кто выиграет?
Решение:
Пронумеруем столбцы слева направо, и строчки сверху вниз. Будем обозначать через (i, j) клетку на пересечении i-ого столбца и j-ой строчки. Играем за первого игрока. Сначала сходим в клетку (2, 2). Теперь, если второй игрок не сходит в клетку (1, 1), то мы сможем сходить в одну из клеток (2, 1) или (1, 2) и тем самым заблокировать для второго игрока клетку (1, 1). Тогда далее будем играть произвольно, не ходя в клетку (1, 1). Если мы в какой-то момент не можем сделать ход, то и второй игрок не может сделать хода. Тогда нам достаточно сходить в клетку (1, 1). Значит, первым своим ходом второй игрок ходит в (1, 1). Тогда сходим далее в клетку (4, 1). Легко видеть, что мы создали себе «запас» в виде клетки (3, 1), в которую мы сможем сходить на любом ходе (второй игрок не может ее заблокировать). То есть снова будем ходить произвольно, пока можем. Если когда-нибудь не сможем, то сходим в (3, 1) и у второго не будет хода.
Ответ:
Первый игрок.
Задача 252. Игра в «В слепую»-II
Состав из конечного числа одинаковых вагонов замкнут в кольцо. Вас с куском мела поместили в один из вагонов. Вы можете свободно ходить по составу и делать любые пометки на стенах вагонов. В любой момент вы можете сказать, сколько вагонов в поезде. Если угадаете, то Вас выпустят. Учтите, однако, что до Вас уже многие пытались пройти это испытание. Возможно, они оставляли на стенах какие-то пометки. Опишите алгоритм, который точно поможет спастись.
Решение:
Пометим вагон, в котором мы оказались какой-нибудь отметкой. Пройдемся по часовой стрелке по составу до тех пор, пока не наткнемся на похожую на нашу пометку, после этого сотрем ее (или зачеркнем), запомним количество вагонов, пройденных от стартовой позиции, и вернемся в начальный вагон, двигаясь против часовой стрелки. Если там пометка оказалась стертой, то мы прошли полный круг и знаем длину состава. Иначе повторим операцию. Вагонов конечное число, поэтому рано или поздно мы сотрем метку в стартовом вагоне и узнаем длину состава.
Задача 253. Игра в «Заполнение доски»-XXIII
Андрей расставляет на ребрах двух одинаковых кубов стрелочки, потом Борис совмещает кубы. Андрей выигрывает, если совпало меньше половины стрелок, Борис если больше, иначе ничья. Кто выигрывает при правильной игре?
Решение:
Докажем, что Андрей может расставить на ребрах двух кубов стрелочки так, чтобы вне зависимости от действий Борис совпала ровно половина стрелочек. Сначала покажем построение на первом кубе. Выделим одну вершину на кубе – скажем, верхний правый угол на верхней грани. Расставим стрелки на ребрах так, чтобы они образовывали поток из этой вершины в диаметрально противоположную. Теперь рассмотрим второй куб. Выделим в нем ту же вершину, сделаем все ребра исходящими из нее. Для каждой из трех смежных с ней вершин сделаем все ребра входящими в нее. Для диаметрально противоположной вершины наоборот сделаем все ребра входящими в нее. Тогда для всех вершин, смежных с диаметрально противоположной, все ребра являются исходящими.
Отметим, что каждая вершина второго куба такова, что либо все ребра из нее исходят, либо все входят. Более того, если в некоторую вершину ребра входят, значит из каждой соседней вершины ребра выходят, и наоборот. Это значит, что результатом любого вращения второго куба может быть только один из двух вариантов расстановки стрелочек: исходный, и такой, который получается из исходного заменой всех стрелочек на противоположные. Первый вариант получается всегда, когда из верхнего правого угла верхней грани ребра исходят, а второй – когда наоборот входят. И нетрудно видеть, что для каждого варианта ровно 6 из 12 стрелочек совпадают с расстановкой на первом кубе.
Теперь докажем, что Борис может всегда действовать так, чтобы после поворота второго кубика совпало хотя бы 6 ребер. Выделим произвольное ребро на первом кубе. Отметим, что второй куб всегда можно повернуть так, чтобы направление на этом ребре у них совпало. Действительно, возможно, оно у них и так совпадает, и поворот не требуется. Иначе, выделим произвольную грань, которой принадлежит это ребро, и рассмотрим композицию поворота на 180° относительно оси, перпендикулярной этой грани, и на 90° относительно оси, параллельной этой грани. Первый поворот переводит ребро в противоположное на выбранной грани, а второй – наоборот, переводит противоположное ребро в исходное. В результате этих двух поворотов получилась расстановка стрелочек, в которой направление выбранного ребра поменялось. Это означает, что из всех способов поворота второго куба ровно у половины направление на выделенном ребре совпадает с направлением на первом кубе, и ровно у половины – нет. Действительно, композиция поворота на 270° относительно оси, параллельной фиксированной грани, и поворота на 180° относительно оси, перпендикулярной этой грани, является обратным преобразованием к композиции выше. Поэтому композиция поворотов выше является взаимно однозначным соответствием, и разбивает все повороты второго куба на пары, в каждой из которых у одного поворота направление на фиксированном ребре совпадает с первым кубом, а у другого – нет.
Рассмотрим всевозможные варианты расстановок стрелочек, полученные поворотом второго куба. Обозначим их количество как n. Просуммируем по всем ним количество совпадающих по направлению ребер с ребрами первого куба. По доказанному выше ясно, что получится число 12×n/2, так как для каждого из 12 ребер ровно половина из n расстановок совпадает с первым кубом по направлению этого ребра. Тогда, по принципу Дирихле, существует расстановка, в которой с первым кубом совпадает по направлению хотя бы 12×n/2/n=6 ребер. Борис достаточно вернуть эту расстановку.
Поскольку у каждого игрока существует стратегия, по которой он не проигрывает, результатом может стать только ничья.
Ответ:
Никто.