Игры

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

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

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

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

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

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

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

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

Сначала приведём стратегию за Соню. Пока она не получила больше 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, либо к числу и выиграть.

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

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

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

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

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

б) А в 24-угольники диаметрально противоположные вершины покрашены в одинаковые цвета, поэтому здесь выигрышную стратегию может применить начинающий: он соединяет противоположные вершины, а далее действует по стратегии, описанной в пункте а).

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

Начнём со стратегии для первого. Пусть он на каждом шаге берёт самое тяжёлое яблоко. Тогда если на м шаге первый взял яблоко с весом а второй — c весом то (на последнем шаге второму может не достаться яблока, если количество яблок нечётное, и в этом случае считаем, что Следовательно, первый однозначно объест второго.

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

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

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

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

Цель первого игрока — добиться появления на доске фишки с весом 1 (т. е. фишки в первой клетке). Когда фишка сдвигается из клетки в клетку ее вес удваивается.

Игра в терминах весов выглядит следующим образом:

1.

Первый игрок разделяет множество всех фишек с общим весом на два подмножества с весами и где

2.

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

Докажем критерий выигрыша в обе стороны.

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

______________________________________________________________________________________________________________________________________________________

Лемма. Любое мультимножество фишек с весами из набора

и суммарным весом можно разбить на два подмножества, вес каждого из которых не менее

Доказательство леммы. Будем последовательно заменять в мультимножестве пары одинаковых дробей (где ) одной дробью Этот процесс не меняет общую сумму и в итоге приведет к мультимножеству, в котором каждая дробь вида (при ) встречается не более одного раза. Если после этого в наборе есть хотя бы две дроби то разбиение очевидно. В противном случае (не более одной дроби ) сумма всех дробей, кроме, возможно, целых, строго меньше

Это противоречит условию, что исходная сумма Значит, после упрощения мы получим либо целую часть, либо достаточное количество дробей для разбиения.

_________________________________________________________________________________________________________________________________________________________________________________

Следуя этой лемме, первый игрок делит фишки на две группы с весами и Второй игрок вынужден выбрать одну из них, и новый суммарный вес станет

Таким образом, суммарный вес фишек никогда не опускается ниже 1. Поскольку на каждом ходу хотя бы одна фишка сдвигается влево, игра конечна. Она не может закончиться исчезновением всех фишек (так как это состояние с весом 0). Следовательно, игра должна закончиться появлением фишки в первой клетке (весом 1).

Случай 2: Докажем, что в этом случае выигрывает второй игрок.

Стратегия второго игрока: после того как первый разделит фишки на группы и выбирать ту, у которой вес меньше. Пусть Тогда так как

Второй игрок оставляет группу и новый вес становится

Так как суммарный вес всегда остается меньше 1, состояние победы для первого игрока (фишка с весом 1) недостижимо.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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