Игры

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

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

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

Приведём выигрышную стратегию для Данила. Число клеток на поверхности чётно (равно Разобьём всю поверхность куба на доминошки; доминошки не пересекаются и покрывают весь куб. Легко видеть, что такие примеры есть. В начале хода Данила пешка стоит в какой-то доминошке. Данил ходит во вторую клетку доминошки. Если Данил до этого действовал в соответствии с этой стратегией, то вторая клетка доминошки не закрашена, и сделать в неё ход можно. Очевидно, что последний ход сделает Данил — хотя бы потому, что он всегда может сделать ход.

Разобьем крестики и нолики на пары (объединим в пары рядом стоящие крестики и нолики). Тогда если сходивший поменял крестик и нолик из разных пар местами, то мы поменяем парные к ним крестик и нолик местами.

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

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

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

1.

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

2.

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

3.

Осталось два квадратика, и они не смежны. Из-за нечётности есть спичка, в них не входящая, которую и возьмёт Вася.

Все позиции рассмотрены.

(a) Пусть Ваня сможет за конечное количество ходов добиться Вначале

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

Иначе Таня вынуждена сделать или и опять-таки Ваня выигрывает.

(b) Стратегия Тани — держать коэффициент при равным 10 или 11.

В этом случае значение многочлена будет не кратно трем и, следовательно, не равно нулю.

Действительно, многочлены

не кратны трем при любом целом

При остаток от деления на три равен 2; при остаток от деления на три составляет 1 и 2, соответственно; при остаток от деления на три составляет 2 и 1, соответственно.

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

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

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

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

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

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

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

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

Рассмотрим ситуацию после седьмого хода (это ход первого), когда свободны остатка. Разберём три случая.

Свободные остатки расположены подряд: Тогда второй выписывает число с остатком (занимает остаток ), первый — а второй и выигрывает.

Остатки расположены так: два рядом — и один отдельно — Тогда второй занимает один из остатков далее либо первый занимает остаток второй — и выигрывает, либо первый занимает а второй — один из оставшихся и выигрывает.

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

Первый способ. Сначала попробуем применить уже известную нам симметричную стратегию для второго игрока. Разобьем все числа на пары: 1 — 1000, 2 — 999, ..., 500 — 501 (то есть пары чисел, которые в сумме дают 1001). Если первый игрок стер число , то второй стирает парное ему число — . То есть после хода второго в каждой паре числа либо оба стерты, либо оба остались. Следовательно, два последних числа будут обязательно из одной пары, то есть их сумма будет ровно , что не делится на 3. Таким образом второй всегда побеждает.

Второй способ. Теперь попробуем порешать эту задачу другим методом. Проанализируем момент, когда какой-то игрок побеждает или проигрывает, то есть последний ход. Так как последний ход четный, то его совершает именно второй игрок. Тогда перед последним ходом второго у нас осталось 3 числа. Какое число нужно выбрать в этот момент второму, чтобы он победил? Ему нужно оставить числа, сумма которых не кратна трем. Обозначим остатки по модулю 3 этих трех чисел за .

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

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

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

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

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

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

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

Играя за Петю, хочется каждый раз брать карточку с наибольшим числом. Однако Вася тоже может брать такие карточки и мешать нам. Поймем, что на первом ходе Петя может взять карточку с числом 10, на втором шаге — с числом хотя бы 8 (хотя бы одна карточка из трех наибольших еще осталась), на третьем — хотя бы 6, на четвертом — хотя бы 4, на пятом — хотя бы 2 (каждый раз берем наибольшую карточку из оставшихся). То есть мы доказали, что Петя всегда может набрать себе хотя бы .

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

Тем самым мы доказали, что Петя всегда может забрать себе 30, а Вася всегда может сделать так, чтобы больше 30 Петя не забрал. Следовательно, наш ответ — ровно 30.

Приведем стратегию, когда Петя может забрать себе все шашки.

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

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

Будем играть за Васю и стараться ходить симметрично Пете относительно центральной клетки. То есть после каждого хода Пети ставим нолик в симметричную клетку, если она свободна. Если симметричная клетка занята, то ставим в любую другую свободную.

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

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

Значит, по такой стратегии .

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

Выделим внутри квадрат и будет работать в нём. Пусть первым ходом Дед Мороз красит центр одного из таких квадратов (ясно, что со всех четырёх сторон от этой клетки он может закрасить ещё хотя бы 2 клетки). Пусть далее Снегурочка красит одну из клеток доски. Если эта синия клетка в одном столбце с красной, то в строке с красной клеткой нет синих. Если эта синия клетка в одной строке с красной, то в столбце с красной клеткой нет синих. Иначе в строке с красной клеткой нет синих.

Пусть в строке нет синих. Дед Мороз покрасит любую соседнюю со своей красной. Далее есть 2 клетки(соседние с получившимся прямоугольником 1 на 2), покрасив любую из которых, Дед Мороз выиграет. Ясно, что за один ход Снегурочка покрасит не более одной из них, и следующим ходом Дед Мороз выигрывает (по сказаному ранее Снегурочка к этому моменту ещё не выиграет). Случай, если нет синих клеток в столбце с красной разбирается аналогично.