Игры

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

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

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

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

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

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

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

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

Пусть - итоговое шестизначное число. Пусть также и . Заметим, что если Боря своим третьим ходом поставит цифру из множества , Аня выиграет, поскольку полученное число будет делиться на 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, так как Оставшиеся числа можно ставить в любые из оставшихся клеток, так как максимальная ещё не рассмотренная сумма будет равна

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

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

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

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

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

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

Чтобы добиться двух рублей, играя за Катю, достаточно раз сказать черный цвет и раз белый. Очевидно, что хотя бы два разноцветных прямоугольника мы так получим.

Играя за Сашу, поделим всю доску на квадратики затем введём шахматную раскраску на них. “Чёрные” квадратики будем красить “вертикально”, то есть на ход Пети закрашивать вторую клетку из вертикальной доминошки, в которую он попал. В “белых” будем действовать аналогично “горизонтально”. В итоге все квадратики будут иметь один из видов (заменим красный и синий цвета на крестики и нолики)

При этом первые два не могут быть рядом (будем звать их горизонтальными), как и (вертикальные), а можно получить в любом квадратике (диагональные). Нетрудно видеть, что при таких условиях из них можно сложить “полосу” не длиннее четырёх крестиков (ширины ). Для этого нужно взять горизонтальный, а затем добавить по бокам вертикальный и диагональный, либо наоборот. Если же рассматривать полосу ширины два, то она не может иметь длину больше двух. Действительно, либо она идёт прямо по квадратику и имеет длину не более одного, либо идёт между квадратиками, тогда хотя бы один из них не является вертикальным (считаем, что полоса ориентирована вертикально), откуда даже её общая часть с ними имеет длину не более единицы. В итоге максимальная длина такой полосы, если она находится на пересечении квадратиков, будет равна площадь — Полоса длины три или четыре (а шире их не бывает) имеет длину не более единицы, поскольку иначе бы существовал квадратик полностью из крестиков либо два горизонтальных/вертикальных были бы рядом. В результате такая стратегия приводит к максимальному выигрышу для Коли.

Чтобы добиться этого выигрыша, Коле нужно покрасить фигуру ниже (можно убедиться, что так сделать можно всегда, если Саша хочет избежать фигуры площади )

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

Стратегия Карлсона будет взять число если если Можно считать, что Карлсон отсчитывает в сторону против часовой стрелки. Пронумеруем блюдца с помощью их остатков по модулю против часовой стрелки, то есть начиная с первого выбранного Малышом. Тогда Малыш получит блюдца при этом Карлсон получает номера то есть забирает у Малыша все блюдца, кроме первых двух. Остаётся заметить, что — простое число, поэтому в последовательности Малыша и, Карлсона все тарелки будут различны. Отсюда Карлсон получит все тарелки, кроме двух, то есть Нетрудно убедиться, что меньше 2 конфет Малыш не получит, иначе тогда Карлсон получит ровно конфету.