Игры

Пронумеруем отмеченные точки подряд остатками при делении на начиная с некоторой точки.

Покажем, что для при любом Вася сможет победить, разбив нужным образом остатки на (одноцветные) пары.

Пусть для данного он пойдет по кругу и будет создавать пары

и т.д., пока в ряду впервые не возникло повторение остатка. Пусть первое повторение — это Повторение где невозможно, так как иначе

и повторение уже случилось шагом ранее. Тогда т.е. Минимальное натуральное с таким свойством — это — степень двойки, большая Значит, четно. Поэтому образуется цикл (четной длины) в котором все остатки разбиты нужным образом на пары.

Так, все остатки разобьем на такие непересекающиеся циклы длины (совмещаемые поворотами окружности), а в каждом цикле разобьем нужным образом остатки на пары.

Пусть где — нечетное число. Покажем, что Вася проиграет, если названо число (оно, очевидно, меньше Предположим, Вася все же сделал требуемое разбиение на пары. Не умаляя общности, считаем, что одна из его пар это (к этому случаю можно прийти, повернув нужным образом окружность). Заметим, что остаток может быть соединен только с так как уже занят. Рассуждая так далее, однозначно восстанавливаем пары

Но уже занят. Противоречие.

Сначала приведём стратегию за Соню. Пока она не получила больше 299 монет, перед её ходом на доске остаётся хотя бы 101 монета. Разобьем доску на 100 квадратов Получается, что какие-то две монеты лежат в одном и том же квадрате Если эти две монеты соседние по стороне, то Соня надвигает одну на другую, и получает ещё одну монету. Если они стоят по диагонали, то Соня сдвигает одну из них в столбец к другой (здесь и далее столбец имеет длину 2, строка — длину 200). Теперь, какой бы ход ни сделала Даша, эти две монетки всё ещё будут соседними по стороне (либо одна будет снята и уйдёт в доход Сони), значит, своим следующим ходом Соня сможет получить ещё одну монетку. Таким образом, Соня всегда сможет увеличивать свой выигрыш, пока он меньше 300.

Теперь покажем, как играть за Дашу, чтобы Соня не получила больше 300 монет. Пронумеруем столбцы числами от 1 до 200 по порядку, выберем в каждом нечётном столбце по одной монетке и мысленно покрасим их в красный цвет. Даше достаточно обеспечить, чтобы красные монетки всегда оставались на доске. Для этого, в свою очередь, достаточно, чтобы две красные монеты никогда не попадали в одну клетку, потому что когда в клетку попадают красная и не красная монеты, можно считать, что с доски снимается не красная.

Назовём расположение монет на доске стабильным, если по одной красной монете лежит в столбцах а ещё одна располагается в одном из двух последних столбцов 199, 200. Легко видеть, что после любого хода из стабильной позиции две красные монеты не окажутся в одной клетке. Даша будет играть так, чтобы после каждого её хода получалась стабильная позиция. Если после хода Сони позиция осталась стабильной, то Даша двигает сотую красную фишку между двумя последними столбцами, так же Даша поступит и своим первым ходом. Если же после хода Сони позиция перестала быть стабильной, то Соня подвинула одну из красных монет из некоторого столбца в соседний столбец. Тогда Даша своим ходом вернёт её в столбец Таким образом, на доске всегда останется хотя бы 100 монет, и Соня заработает не более трёхсот рублей.

Опишем выигрышную стратегию Васи. Пусть Вася все время пишет букву «Ю» в клетку согласно следующим ниже условиям; а если указанная клетка не существует или уже занята, а также если Петя ставит любую букву отличную от «П», «Е», «Т», «Я», то пусть Вася ставит «Ю» в любую свободную клетку.

Если Петя в некоторой клетке пишет букву «П», то Вася пишет «Ю» в клетке, соседней с ней справа; если Петя пишет букву «Е», то Вася пишет «Ю» в клетке, соседней с ней слева; если Петя пишет букву «Т», то Вася пишет «Ю» в клетке, соседней с ней снизу; если Петя пишет букву «Я», то Вася пишет «Ю» в клетке, соседней с ней сверху.

Из первых двух условий следует, что в двух соседних по горизонтали клетках не могло появиться «ПЕ», читаемое слева направо. В самом деле, предположим, что горизонтальное «ПЕ» появилось; тогда после появления первой из этих двух букв Вася, согласно описанной стратегии, сразу займёт место второй из этих букв — противоречие. Аналогично, в двух соседних по вертикали клетках не могло появиться «ТЯ», читаемое сверху вниз.

Заменим все числа в строке на их остатки от деления на 3, от этого результат игры не изменится. Получим строку …, Промежутки между числами пронумеруем слева направо от 1 до 59. Первым ходом Игорь ставит знак минус в 30-й промежуток, а все остальные промежутки он разбивает на пары вида Если Руслан ставит в какой-то промежуток знак плюс или минус, то Игорь в парный промежуток ставит минус или плюс соответственно. А если Руслан ставит знак умножить, то Игорь ставит в парный промежуток также знак умножить. Когда все знаки расставлены, полученное выражение разбивается на несколько слагаемых. При этом в левой и правой половинах выражения набор слагаемых одинаковый, но берутся они с противоположными знаками. Следовательно, его значение будет давать остаток 0 при делении на 3.

Обозначим записанные по кругу числа …, Вася будет следить лишь за десятью числами, которые он разобьёт на пары: …, За один ход Петя может уменьшить не более, чем одно из этих 10 чисел. Если Петя уменьшил одно из чисел пары Вася в ответ добавит 1 к числам …, Если же Петя не уменьшил ни одно из этих 10 чисел, Вася сделает любой разрешённый ход. Таким образом, после пары ходов Пети и Васи сумма чисел в каждой из пяти Васиных пар не уменьшится. Поскольку изначально пять сумм в парах положительны, то после каждого Васиного хода сумма в каждой из этих пяти пар будет положительной, поэтому в каждой из пар будет хотя бы одно положительное число. Таким образом, после любого Васиного хода будет хотя бы 5 положительных чисел, что и требовалось.

Будем играть за Петю. Первым ходом возьмём 3. Используем стратегию дополнения до числа, сравнимого с 3 по модулю 11: если волк взял то мы Таким образом, после нашего го хода на доске будет записано После хода волка остаток по модулю 11 не может стать 7, значит, 2020 у него получиться не может. На 368-м ходу Петя получит 4040 и выиграет.

Будем называть число выигрышным, если при начале игры с него выигрывает первый игрок, и проигрышным, если второй. Число является выигрышным тогда и только тогда, когда существует ход из него в проигрышное число, а проигрышным — тогда и только тогда, когда любой ход из него ведёт в выигрышное число.

Пользуясь этим утверждением, можно, рассматривая натуральные числа последовательно, выяснить для любого конкретного числа, является оно выигрышным или проигрышным:

• число  — проигрышное,
• число  — выигрышное,
• число  — проигрышное (так как единственный ход из него ведёт в выигрышное число ),
• число  — выигрышное (так как из него есть ход в проигрышное число ),

и так далее.

Заметим, что число является проигрышным, следовательно, простое число является выигрышным. Число  — выигрышное: из него можно перейти в проигрышное число Поэтому число хоть и составное, является проигрышным (все три хода из него: и  — ведут в выигрышные числа).

Докажем, что 2 и 17 — единственные выигрышные простые числа. Предположим, что это не так, и рассмотрим следующее выигрышное простое число В таком случае  — проигрышное чётное число, поэтому среди делителей не может быть простых чисел, кроме и Но тогда от него можно перейти либо к числу 34, либо к числу и выиграть.

Если составное число имеет простой делитель отличный от и то из него есть ход в проигрышное число то есть число является выигрышным. Остались числа вида

Нетрудно убедиться, что , ,  — выигрышные, а  — проигрышное, поэтому числа при  — выигрышные: от них можно перейти к

Число  — проигрышное, поэтому числа вида при  — выигрышные: от них можно перейти к

Число  — проигрышное, поэтому числа при  — выигрышные, так как от них можно перейти к

По правилам игры ничьих не бывает, поэтому либо первый игрок, либо второй имеет выигрышную стратегию. Первый игрок может “передать ход” второму, вычеркнув первым ходом Действительно, пусть второй вычёркивает число и все его делители. После этого хода вычеркнуты те числа, какие были бы вычеркнуты, если бы первый игрок первым своим ходом вычеркнул (и все его делители). Поэтому у второго игрока не может быть выигрышной стратегии: первый игрок, “передав ход”, может играть, следуя любой стратегии второго игрока. Значит, выигрышная стратегия есть у первого игрока.

Игра конечна, следовательно, у одного из игроков есть выигрышная стратегия. Докажем, что у второго не может быть выигрышной стратегии. Предположим, что она у него есть, и будем играть за первого. Первым ходом выбросим кучку а вторую разделим на и Второй игрок обязательно выбросит кучку и разделит как-то кучку С этого момента у второго игрока есть ответные ходы на каждый наш ход, соответствующие выигрышной стратегии. Тогда можем начать игру по-другому: первым ходом выбросим кучку и разделим кучку так же, как и второй игрок разделил бы ее в соответствии со своей выигрышной стратегией. Теперь будем отвечать на ходы второго по его же стратегии и победим. Значит, у первого тоже есть выигрышная стратегия. Противоречие.

Доказали, что первый игрок имеет выигрышную стратегию.

Первый игрок напишет число второй число Далее первый может написать число а может написать число и тогда второй напишет число После написания числа выигрышная стратегия есть либо у ходящего, либо у его противника. Так как первый игрок после написания числа может по своему желанию оказаться и ходящим, и противником ходящего, он может воспользоваться выигрышной стратегией. Таким образом мы доказали, что у первого есть выигрышная стратегия.

Для выигрыша ему достаточно до самого конца объединять имеющиеся кучки так, чтобы была одна большая кучка и несколько кучек по одному ореху. При такой стратегии сохраняется инвариант — нечетность максимальной кучки после хода второго. В случае нечётного второй придерживается такой стратегии до конца, а в случае чётного — до позиции из четырёх кучек и после чего на любой ход первого: или — отвечает ходом

Докажем, что для любого натурального первый игрок на своём -ом ходе может добиться, чтобы количество забранных из кучки камней равнялось , и второй игрок не сможет ему помешать. Доказательство проведём индуктивно.

В свой первый ход первый игрок забирает один камень, т. е. число забранных камней равно . Пусть в свой -й ход первому игроку удалось сделать так, чтобы количество забранных камней равнялось . В свой -й ход второй игрок может взять от до камней. Поскольку после его хода общее количество забранных камней будет больше и меньше . Первый игрок в свой следующий ход может взять от до камня и точно сможет получить забранных камней независимо от предыдущего хода второго игрока.

Таким образом, поскольку , побеждает первый игрок: ему достаточно каждый раз забирать такое число камней, чтобы общее число забранных камней было точным квадратом, и на своём ходе он возьмёт последний камень.

Пусть - итоговое шестизначное число. Пусть также и . Заметим, что если Боря своим третьим ходом поставит цифру из множества , Аня выиграет, поскольку полученное число будет делиться на 2 . Значит, .

Пусть Аня первым ходом выберет цифру , а вторым ходом - цифру 9. Если Боря на первом или втором ходу выберет цифру из множества , то своим третьим ходом Аня заберет последнюю оставшуюся цифру из множества , и Боря вынужден будет взять свою цифру из , что приведет к его проигрышу. Значит, Боря вынужден взять первые две свои цифры и взяты из множества . Заметим, что Боря вынужден будет на последнем ходе выбрать либо цифру 1 , либо цифру 7 , которые дают одинаковый остаток 1 при делении на 3. Поэтому Ане достаточно подобрать цифру так, чтобы сумма цифр давала бы остаток 2 при делении на 3 . Поскольку и не влияют на остаток этой суммы, все зависит от остатка суммы . Покажем, как действовать Ане в каждом из случаев.

Если делится на 3 , то Аня выберет цифру из набора : поскольку до этого момента эти цифры мог выбирать только Боря, как минимум одна из этих трех цифр останется не выбранной.

Если дает остаток 1 при делении на 3 , Аня выберет цифру . Как мы помним, Боря не мог ее выбрать на первых двух ходах.

Наконец, если дает остаток 2 при делении на 3 , Аня выберет цифру из набора . Боря не мог выбрать обе эти цифры, поскольку тогда , а мы предположили, что дает остаток 2 при делении на 3 .

Таким образом, Аня выиграет.

Заметим, что то есть Вася может делить только на или , а Петя —– только на четные числа (вида или , где ) То есть Вася проигрывает, когда заканчиваются все пятерок, а Петя —– когда заканчиваются все двоек. Причем Вася может забирать только свои пятерки, а Петя может забирать как двойки, так и пятерки.

Значит, Петя может быстрее приблизить Васю к проигрышу, когда будет забирать его пятерки. Действительно, Петя может первым ходом поделить число на а затем каждым ходом будет делить число на доске на Не позднее, чем после ходов Васи пятерок не останется (но двоек будет хотя бы , так как забирает их только Петя), значит, Вася не сможет сходить, а Петя выиграет.

Покажем стратегию игры за Васю. Каждым ходом будем двигать фишку на 1 клетку, если Петя своим предыдущим ходом подвинул ее на 2 клетки, и на 2 в противном случае.

Докажем, что данная стратегия является выигрышной. После каждой пары ходов Пети и Васи фишка будет передвинута на 3 клетки, следовательно, после хода Васи фишка будет передвинута на клеток. Наконец, после 33 хода фишка будет передвинута на 99 клеток и окажется в последней.

Очевидно, что Васе нужна стратегия, в которой он не более двух раз “проваливается”, то есть называет число, большее задуманного Петей (так как после третьего "провала"весь фонд уходит Пете). Сначала предложим стратегию, позволяющую Васе гарантированно получить указанное количество фунтиков, а потом докажем, что это максимальное количество, которое он может гарантировать.

Стратегия Васи с одним “провалом”: пусть (т.е. наименьшее натуральное , при котором ). Шаги до “провала”: Вася называет числа пока Петя не скажет, что для очередного (первый "провал") или что угадано число Сумма арифметической прогрессии а значит, такой момент обязательно наступит. Если это в момент первого “провала”, то в этот момент Петя получает из фонда фунтиков, в фонде остаётся фунтиков, а Вася приступает к выполнению шагов до "угадал".

Шаги до “угадал”: Вася называет (не более чем последовательные числа от до (которое меньше ) до тех пор, пока Петя не скажет, что задуманное число угадано, а Вася, сыграв раундов, получает из фонда фунтиков.

Докажем, что такая стратегия оптимальна. Пусть существует стратегия для Васи, позволяющая гарантированно получить больше фунтиков. Эта стратегия предписывает возрастающую последовательность чисел где и для любого Но так как то а значит, остались непроверенные числа от до и такая стратегия не может гарантированно улучшить результат.

Очевидно, что достаточно рассмотреть случай, когда игрок, делающий первый ход, заполняет максимально возможное число ячеек, равное . Расположим эти число в порядке не убывания: . Здесь в индексах указаны номера позиций, на которых стоят эти числа в таблице. Образуем два множества позиций, которые заполнены: и , беря указанные числа через одно. Тогда суммы чисел на этих позициях могут отличаться друг от друга не более, чем на 2022. Поэтому оставшуюся незаполненной позицию можно заполнить числом от 0 до 2022 так, чтобы получилась «счастливая» комбинация.

Расположим камни в клетки таблицы на так, что главная диагональ была пустой (столбцы будут кучами). Петя должен брать несколько камней из одного столбца, а Вася — из разных. Тогда заметим, что если Вася будет делать ходы симметричные Петиным относительно пустой главной диагонали, то условие будет выполняться. Поэтому у Васи всегда есть ход. Так как игра конечна, то когда-то Петя проиграет.

Давайте разобьём клетки на пары следующим образом. Каждой клетке не из главной диагонали поместим в пару клетку, симметричную ей относительно главной диагонали. Клетке на главной диагонали, отличной от центральной, поставим в соответствие клетку из главной диагонали, симметричную ей относительно центральной. Центральная клетка останется без пары.

Теперь приведём стратегию за Игоря. Пусть первым ходом он покрасит центральную, а дальше на каждый ход второго будет отвечать ходом в парную клетку. Нетрудно заметить, что клетки в парах находятся в разных столбцах и строках, а значит, Игорь всегда сможет сделать ход.

Докажем, что Маша может выиграть независимо от действий Паши. Пусть она своим первым ходом соединит отрезком любые две противоположные вершины -угольника, проведя диагональ Заметим, что теперь ни один из игроков не может проводить диагонали, симметричные сами себе относительно этого отрезка (такая диагональ перпендикулярна первой проведенной). Пусть далее Маша будет делать ходы, симметричные ходам Паши относительно первой проведенной диагонали. Докажем, что такой ход возможен.

Рассмотрим произвольный момент, когда Паша будет делать очередной ход, проведя диагональ До этого момента была проведена диагональ для некоторого целого Тогда очередная Пашина диагональ должна пересечь хотя бы ранее проведенную. Следовательно, Машина симметричная диагональ также пересечет хотя бы ранее проведенную диагональ. При этом диагональ может быть перпендикулярна только диагонали проведенной Пашей ходом ранее. Значит, у нас образовались две перпендикулярные диагонали, симметричные относительно диагонали Тогда длины этих диагоналей равны. То есть они отличаются друг от друга поворотом на угол для некоторого целого откуда что невозможно, так как не делится на