Задача 191. Игра в «Камешки»-XI
Двое игроков по очереди (пропускать ход нельзя!) выставляют на стол либо одну фишку, либо столько, сколько их уже стоит на столе, если нужное число фишек еще осталось в коробочке. Выигрывает тот из них, кто поставит последнюю фишку. В начале игры на столе фишек нет, а в коробочке — 11. Кто выиграет, если будет играть наилучшим образом?
Решение:
Всего 11 фишек. Во время первого хода первый и второй игроки кладут на стол по одной фишке, в коробочке остается 9 фишек. Предположим, что выиграет первый игрок (он должен положить последнюю фишку). Значит, каждый раз после хода первого игрока на столе должно оставаться нечётное количество число фишек, а после хода второго игрока — четное (нечет + нечет = чет или нечет + 1 = чет). Просчитаем все возможные варианты игр, учитывая наши предположения:
Вывод: предположение верно. Если после хода первого игрока остаётся нечётное количество фишек, то он обязательно выигрывает.
Ответ:
Если первый игрок будет играть наилучшим образом (после его хода остаётся нечётное количество фишек), то он выиграет.
Задача 192. Игра в «Числа»-X
Двое играют в такую игру. Они по очереди называют четырёхзначные числа, у которых нет нулей в записи, а сумма цифр делится на 9. При этом каждое следующее число должно начинаться с той же цифры, на которую кончается предыдущее, например: 3231 — 1539 — 9756 — 6561 ... Повторять числа нельзя. Тот, кто не может назвать очередное число, проигрывает. Кто из игроков — начинающий или его соперник — может выиграть независимо от игры другого?
Решение:
Выигрывает первый игрок. Одна из возможных стратегий такова. Он называет число 9999, а потом в ответ на любое число ABCD названное вторым, называет число DCBA то же самое число «задом наперёд». Заметим, что после этого второму опять придётся назвать число, которое начинается на 9. Первый игрок всегда может сделать ход, ведь подходящих чисел вида 9BB9 (кроме 9999) больше нет.
Замечание. В качестве начального числа первый игрок может использовать любой другой палиндром (то есть число, читаемое в обоих направлениях одинаково): 1881, 2772 и т. д.
Ответ:
Начинающий.
Задача 193. Игра в «Числа»-XI
Имеется круглый стол с 16 секторами, на которых по кругу написаны числа 0, 1, 2, …, 7, 8, 7, …, 2, 1. За столом сидят 16 игроков, пронумерованных по порядку. После каждого вращения стола каждый игрок получает столько очков, сколько написано на секторе, за которым он оказался после остановки стола. Оказалось, что после 13 вращений стола игрок под номером 5 набрал 72 очка, а игрок под номером 9 в сумме 84 очка. Сколько очков набрал игрок под номером 1?
Решение:
Игроки №5 и №9 вместе набрали:
72+84=156=13×12.
За одно вращение они могут вместе получить не более 12 очков. Значит, в каждом из 13 вращений они вместе получили 12 очков. Заметим, что 12 очков они получают в виде одной из сумм 8+4, 7+5, 6+6, 5+7 или 4+8, когда сектор 8 оказывается перед одним из них или между ними, то есть перед одним из игроков с номерами 6, 7, 8. В каждом из этих пяти случаев игрок №1 получает соответственно 4, 3, 2, 1 или 0 очков. Это можно выразить формулой:
Х1=(Х5-Х9)/2+2,
где Хn – количество очков за это вращение у игрока с номером n. Тогда количество очков игрока №1 после 13 вращений равно:
(72-84)/2+2×13=20.
Ответ:
20.
Задача 194. Игра в «Числа»-XII
Андрей и Борис играют в игру. У них есть полоска из 10 клеток. Каждым ходом игрок вписывает любую цифру в любую свободную клетку. Однако ходят они не по очереди. Сначала Андрей делает столько ходов, сколько захочет (но меньше 10); потом он просит Бориса сделать один ход; после этого Андрей делает все оставшиеся ходы. Андрей выиграет, если результирующее число окажется точным квадратом; в противном случае выигрывает Борис. При этом они считают, что число может начинаться с одного или нескольких нулей. У кого из игроков есть выигрышная стратегия?
Решение:
Выигрышная стратегия есть у Андрея. Например, такая: он пишет в двух последних клетках 04. Заметим, что если число кончается на 02 или 52, то его квадрат кончается на 04. Докажем, для любого хода Бориса Андрей сумеет найти точный квадрат.
Пусть Борис сходил в разряд сотен. Рассмотрим квадраты чисел 2, 52, 102, 152, 202, 252, 302, 352, 402, 452. Найдём разность между двумя соседними квадратами:
(50a+2)^2=2500a^2+200a+4
(50a+52)^2=2500a^2+5200a+2704
откуда
(50a+52)^2-(50a+2)^2=5000a+2700=700 mod 1000.
Значит, цифра сотен каждого следующего из этих чисел получается из предыдущего увеличения на 7 по модулю 10. Следовательно, цифры сотен во всех этих числах разные (0, 7, 4, 1, 8, 5, 2, 9, 6, 3). Поэтому, если Борис сходит в разряд сотен, Андрей сумеет дополнить число до квадрата.
Пусть Борис сходил в разряд тысяч, то есть имеем число ******xy04, где x задано Борисом. Рассмотрим ряд чисел
(100a+2)^2=10000a+400a+4,
где a=0, 2, …, 24. В этих числах xy образуют арифметическую прогрессию с разностью 4 (04, 08, 12, ..., 96), поэтому для каждого x найдётся подходящий y.
Если Борис сходил в десятки тысяч, то рассуждения аналогичные: среди квадратов
1ǀ004ǀ004, 4ǀ008ǀ004, 9ǀ012ǀ004, 16ǀ016ǀ004, 25ǀ020ǀ004, …, 576ǀ096ǀ004
найдутся подходящие. Если Вася сходил в разряд сотен тысяч или больший, то такие рассуждения приводят к рассмотрению слишком больших чисел, но работает другая идея: попытаемся сделать цифру Бориса первой ненулевой цифрой в нашем числе.
Заметим, что квадраты соседних чисел в ряду
2, 52, …, 902, 952
различаются менее чем на 100 000 (это следует из формулы квадрата суммы), 9522 > 900000, а поэтому цифра сотен тысяч пробегает в них все значения от 0 до 9. В ряду
2, 52, … 2902, 2952, 3002
квадраты соседних чисел различаются менее чем на миллион, а последний превышает 9 миллионов; значит, цифра миллионов пробегает все значения от 0 до 9.
Три старших разряда рассмотрим одновременно. В ряду
2, 52, …, 99902, 99952
квадраты соседних чисел различаются менее чем на 10 миллионов, а в числе
999522=9990402304
во всех трёх старших разрядах стоят девятки. Значит, каждый из трёх старших разрядов пробегает все значения от 0 до 9.
Ответ:
У Андрея.
Задача 195. Игра в «Крестики-нолики»-I
Правила интересной игры в крестики-нолики следующие. По окружности, чередуясь, расположено n крестиков и n ноликов. За ход разрешается поменять местами крестик и нолик, если только соответствующие знаки еще не менялись друг с другом местами. Если после хода игрока образовалось три одинаковых знака подряд, то он проиграл. Также проигрывает игрок, не имеющий хода. Андрей и Борис играют в интересные крестики-нолики, Андрей начинает. Кто выигрывает при правильной игре в зависимости от n?
Решение:
Разобьем крестики и нолики на пары (объединим в пары рядом стоящие крестики и нолики). Тогда если сходивший поменял крестик и нолик из разных пар местами, то мы поменяем парные к ним крестик и нолик местами.
Важно, что пары при этом у нас сохранятся, поэтому любая пара либо не менялась вообще, либо в ней поменялись и крестик, и нолик, поэтому ход у нас будет. Если же внутри пары меняют крестик и нолик, то мы возьмем другую пару и поменяем в ней крестик и нолик. Но вот осталась ли у нас пара или нет уже зависит от n. Если n четно, то описанной стратегией мы будем играть за второго, так как тогда после хода второго оставшихся пар всегда будет четно, а значит у второго всегда будет ход. Если n нечетно, то этой же стратегией играем за первого игрока, только первым ходом меняем крестик и нолик из одной пары, тогда пар останется четно, а дальше после хода первого пар всегда будет четно и у первого всегда будет ход.
Осталось понять, почему у нас не образовалось три крестика или три нолика подряд при такой стратегии (при любом n). Тут надо заметить, что мы ходим так, что пары крестик и нолик остаются в своих же парах (после хода того, за которого мы играем), но, если бы у нас образовались три крестика или три нолика подряд, это бы означало, что нашлась бы пара, в которой два крестика или два нолика, но такого быть не могло. Таким образом, стратегия работает.
Ответ:
Андрей при нечётном n, Борис при чётном.
Задача 196. Игра в «Числа»-XIII
На доске записаны числа 1, 2, 3, …, 1000. Двое по очереди стирают по одному числу. Игра заканчивается, когда на доске остаются два числа. Если их сумма делится на три, то побеждает тот, кто делал первый ход, если нет — то его партнер. Кто из них выиграет при правильной игре?
Решение:
Первый способ. Сначала попробуем применить уже известную нам симметричную стратегию для второго игрока. Разобьем все числа на пары: 1 — 1000, 2 — 999, ..., 500 — 501 (то есть пары чисел, которые в сумме дают 1001). Если первый игрок стер число x, то второй стирает парное ему число — 1001-x. То есть после хода второго в каждой паре числа либо оба стерты, либо оба остались. Следовательно, два последних числа будут обязательно из одной пары, то есть их сумма будет ровно 1001, что не делится на 3. Таким образом второй всегда побеждает.
Второй способ. Теперь попробуем порешать эту задачу другим методом. Проанализируем момент, когда какой-то игрок побеждает или проигрывает, то есть последний ход. Так как последний ход четный, то его совершает именно второй игрок. Тогда перед последним ходом второго у нас осталось 3 числа. Какое число нужно выбрать в этот момент второму, чтобы он победил? Ему нужно оставить числа, сумма которых не кратна трем. Обозначим остатки по модулю 3 этих трех чисел за x, y, z.
Если среди них есть хотя бы два различных (пусть x и y), то хотя бы одно из чисел x+z и y+z не кратно трем (если оба кратны трем, то x и y совпадают с остатком числа z). Значит, у второго точно есть ход, после которого он побеждает.
Значит, второй может проиграть, только если все три остатка равны, причем равны нулю (иначе сумма любых двух чисел не кратна трем, то есть второй обязательно побеждает). Тогда второму нужно не допустить такую ситуацию. Что нужно сделать, чтобы в конце точно не осталось трех нулей? Давайте каждым ходом второго игрока стирать числа, кратные трем (если такие еще есть). Тогда к последнему ходу второго вовсе не останется чисел, кратных трем (так как их сильно меньше половины всех чисел). То есть ситуации с тремя нулями точно не будет, и значит, второй победит.
Ответ:
Второй.
Задача 197. Игра в «Числа»-XIV
На столе лежат карточки, на которых написаны по разу все делители числа 2000000, причем на каждой карточке написан один из делителей. Два игрока по очереди берут себе по одной карточке. Проигрывает тот, у кого число на одной из его карточек делится на число на другой из его карточек. Кто выигрывает при правильной игре?
Решение:
Поделим все карточки на пары: d и 2000000/d. Все карточки так разобьются, так как 2000000 не является квадратом. Будем играть за второго и брать каждым ходом парную карточку к карточке первого. Если вдруг у нас оказались два числа x и y такие, что x кратно y, то у нашего соперника уже было два числа 2000000/x и 2000000/y , причем 2000000/x кратно 2000000/y , так как 2000000/x : 2000000/y как x:y— целое, так как x кратно y, то есть первый бы уже проиграл. Значит, у нас всегда есть ход, а так как игра конечна, то мы выиграем.
Ответ:
Второй.
Задача 198. Игра в «Камешки»-XII
На столе лежит
(a) 100 спичек;
(b) 101 спичка.
Андрей и Вася играют в следующую игру, делая ходы по очереди. Начинает Андрей. За один ход можно взять 1, 2, 3 или 4 спички со стола. Выигрывает игрок, взявший последнюю спичку. Кто из игроков может выиграть, как бы ни играл соперник?
Решение:
Используем стратегию дополнения: после каждого нашего хода будем пытаться оставить число спичек, кратное 5. Действительно, если в данный момент число спичек делится на 5, то соперник никак не сможет оставить количество, кратное 5. Если же спичек не кратно 5, то мы можем взять остаток от деления на 5. Ясно, что после хода соперника 0 спичек остаться не может. Значит, если спичек изначально кратно 5, то победит Борис, а иначе — Андрей.
Ответ:
a) Борис б) Андрей
Задача 199. Игра в «Камешки»-XIII
Есть куча из n спичек. Разрешается брать от 1 до 10 спичек, выигрывает взявший последнюю спичку. При каких n выигрывает начинающий?
Решение 1. Проанализируем выигрышные и проигрышные позиции. Понятно, что все числа от 1 до 10 — выигрышные.
Число 11 — проигрышное, так как из нее можно попасть только в выигрышные позиции 1–10. Позиции 12–21 — выигрышные, ведь из них можно попасть в 11. Число 22 — проигрышное, и так далее.
Легко видеть, что все позиции, кратные 11, являются проигрышными, а остальные — выигрышными.
Тогда, в силу симметричности позиции перед ходом Бориса, число Андрея отличается от чисел в своей строке и своем столбце. Осталось лишь отметить, что игра конечна, а раз у Андрея всегда есть ход, то он не проиграет, а значит, победит.
Еще раз хочется обратить внимание на то, как мы определяем, является ли позиция выигрышной или проигрышной: для того, чтобы позиция была выигрышной, достаточно ОДНОГО хода, ведущего в проигрышную позиция, а вот чтобы позиция была проигрышной, ВСЕ ходы должны вести в выигрышные. И во время решения мы ровно это и определяем.
Другой подход — дополнение хода соперника до определенного значения.
Решение 2. При количестве спичек, кратном 11, будем играть за второго игрока, дополняя количество спичек, взятых на предыдущем ходу первым игроком, до 11. Другими словами, если первый игрок только что взял x спичек, то мы берем 11-x. Сразу отметим, что количество спичек, которое мы должны брать в ответ на ход первого, также от 1 до 10, то есть с этим проблем не возникает. Кроме того, после нашего хода количество спичек после пары ходов — соперника и нашего — кратно 11, поэтому последнюю спичку заберет именно второй игрок.
При количестве спичек, не кратном 11, играем за первого игрока. Первым ходом берем столько спичек, чтобы количество оставшихся спичек было кратно 11, а дальше повторяем предыдущую стратегию.
Ответ:
При n, не кратных 11.
Задача 200. Игра в «Числа»-XV
Есть 101 клетка. Двое поочередно слева направо вписывают в эти клеточки по одной из цифр от 0 до 9. Если после заполнения всех клеток сумма всех записанных цифр будет делиться на 11, то выиграет игрок, ходивший первым, а если не будет делиться на 11 — то вторым. Какой из игроков выиграет при правильной своей игре и любой игре соперника? Ответ обосновать.
Решение:
Заметим, что первый игрок всегда может дописывать к предыдущему числу второго такое, что их сумма равна девяти. Тогда в парах (2,3), … (100,101) сумма будет равна девяти, откуда вся сумма в клетках 2,3…101 равна 50×9=450 (остаток от деления на 11= -1). Выберем цифру в первой клетке, равной 1 и вся сумма будет кратна 11 при любой игре второго.
Ответ:
Первый