Игры

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заметим, что пока не все клетки покрыты, у первого всегда есть ход. Клеток всего а после ходов второго их количество кратно Значит, у первого всегда будет ход и он победит. В качестве стратегии будем ходить в первую попавшуюся клетку.

Назовём треть веса колбасы фунтом. Покажем, как Хасан может получить не менее фунтов. Сначала он делит колбасу на кусок A в фунт и кусок B в фунта. Если Жасан разделит B, то получатся части весом больше фунта и меньше фунта, поэтому Жасан достанется кусок A в фунт, а Хасану — остальное. Если же Жасан разделит кусок A, то кусок B останется самым большим и достанется Хасану, то есть Хасан получит даже больше фунтов. Покажем, как Жасан обеспечит себе не менее фунта. Когда Хасан разрежет колбасу на два куска, Жасан посмотрит, есть ли среди них кусок в фунт. Если есть, то он режет другой кусок на две части. Если нет, то Жасан от большего куска отрезает фунт. В обоих случаях получаться три куска: меньше фунта, ровно фунт и больше фунта, и Жасану достанется фунт.

Лемма. а) На доске выбраны 11 произвольных клеток. Тогда среди них можно найти три клетки такие, что от одной из них можно двумя ходами ладьи обойти вторую и третью клетки.

б) На доске, суммарное числом столбцов и строк в которой не более 11, выбраны 8 клеток. Тогда среди них можно найти три клетки такие, что от одной их них можно двумя ходами ладьи обойти вторую и третью клетки.

Доказательство леммы. Если в столбце/строке выбрана одна клетка, будем называть её одиночной, а если две — будем называть каждую из двух клеток парной. Будем говорить, что клетка занимает строку/столбец, если она стоит в этой строке/столбце. Заметим, что никакие другие клетки не могут быть выбраны в столбце/строке, где стоит одиночная или парная клетки. Тогда каждая пара клеток занимает суммарно 3 строки и столбца, а каждая одиночная — 1 строку и 1 столбец.

a) Обозначим число одиночных клеток за а число парных клеток — за Если лемма не выполняется, то нельзя 11 клетками занять более 8 строк и 8 столбцов, то есть 16 в сумме. Тогда имеем систему

Но — противоречие. Следовательно, предположение неверно и пункт а) леммы доказан.

б) Аналогично пункту а) леммы обозначим число одиночных клеток за а число парных клеток за — Если лемма не выполняется, то нельзя 8 клетками занять более 11 строк и столбцов в сумме. Тогда имеем систему

Но — противоречие. Следовательно, предположение неверно и пункт б) леммы доказан.

_________________________________________________________________________________________________________________________________________________________________________________

Рассмотрим 11 клеток с числами от 54 до 64. Из пункта а) леммы следует, что какие-то три из них второй игрок может обойти, придерживаясь условий задачи. Минимальная сумма трёх из этих чисел равна

значит второй игрок всегда может получить сумму не менее 165 . Предположим, что сумму больше 165 не всегда удастся получить. Тогда никакие три из клеток с числами от 54 до 64 помимо 54, 55, 56 не должны оказаться в одной строке/столбце или образовывать "угол".

При этом числа 54, 55, 56 обязаны оказаться в одной строке/столбце или образовывать "угол иначе найдётся другая тройка чисел с большей суммой. Если эти числа располагаются в одной строке/столбце, или образуют "угол то занимают суммарно 4 строки и столбца. Без ограничения общности, пусть эти числа стоят так, как показано ниже, ведь если поменять какие-то строки/столбцы местами, искомая сумма не изменится.

И в том, и в другом случае оставшиеся 8 клеток с числами от 57 до 64 располагаются в выделенном прямоугольнике, количество строк и столбцов в которых суммарно равно 12. Если эти 8 клеток занимают не все строки или столбцы, то они занимают суммарно не более 11 строк и столбцов. Тогда из пункта б) леммы следует, что какие-то три числа стоят в одной строке/столбце или образуют “угол”, а значит, выбрав эти три клетки, мы увеличим искомую сумму. Если эти 8 клеток, среди которых одиночных и парных клеток, занимают все строки и столбцы, то имеем систему

откуда Следовательно, все клетки в выделенном прямоугольнике парные. Тогда найдётся число не менее 52 (на второй таблице число 53 может дополнять серые клетки до квадрата), которое стоит в одной строке или в одном столбце с какой-то парной клеткой из выделенного прямоугольника. Взяв это число и две парные клетки, получим сумму не менее Значит, примера, гарантирующего сумму 165, но не гарантирующего сумму 166, не существует.

Пример, гарантирующий сумму 166, но не гарантирующий сумму 167:

Здесь сумма 166 достигается, например, на числах 54, 55, 57. Все остальные суммы в пределах правого нижнего прямоугольника не превосходят 166. Максимальная сумма в пределах правого нижнего прямоугольника не будет превосходить 166, так как Оставшиеся числа можно ставить в любые из оставшихся клеток, так как максимальная ещё не рассмотренная сумма будет равна

Пронумеруем столбцы слева направо, и строчки сверху вниз. Будем обозначать через клетку на пересечении -ого столбца и -ой строчки. Играем за первого игрока. Сначала сходим в клетку . Теперь, если второй игрок не сходит в клетку , то мы сможем сходить в одну из клеток или и тем самым заблокировать для второго игрока клетку . Тогда далее будем играть произвольно, не ходя в клетку . Если мы в какой-то момент не можем сделать ход, то и второй игрок не может сделать хода. Тогда нам достаточно сходить в клетку . Значит, первым своим ходом второй игрок ходит в . Тогда сходим далее в клетку . Легко видеть, что мы создали себе «запас» в виде клетки , в которую мы сможем сходить на любом ходе (второй игрок не может ее заблокировать). То есть снова будем ходить произвольно, пока можем. Если когда-нибудь не сможем, то сходим в и у второго не будет хода.