Анализ позиций

Рассмотрим момент после третьего хода (когда выписаны три числа). Если к этому моменту никто еще не выиграл, то следующим ходом Вася выигрывает — ему достаточно найти два выписанных числа одной чётности и выписать своим ходом их среднее арифметическое (оно является целым числом).

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

Теперь опишем выигрышную стратегию Васи.

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

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

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

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

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

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

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

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

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

Докажем, что Андрей может выпить литра сока, как бы ни действовала Маша, и покажем, что Маша может ходить так, что тоже выпьет литра.

Предположим, Андрей выпил менее литров, то есть смог сделать не более ходов. Тогда Маша сделала не более ходов. Значит, на данный момент выпито не более то есть не выпито хотя бы мл сока.

С другой стороны, так как объёмы всех ёмкостей делятся на то и количество оставшегося сока в каждой упаковке делится на Если Андрей не может сделать ход, то оно не превосходит мл в каждой упаковке, но тогда сока осталось не более мл. Значит, Андрей при любых обстоятельствах сможет сделать ходов.

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

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

Значит, никто не может обеспечить себе победу.

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

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

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

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

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

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

Заметим, что Приведём пример Пашиных чисел, при которых требуемое выполняется. Пусть среди его чисел двоек, чисел, равных а остальные — единицы.

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

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

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

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

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

Таким образом, выигрывает Илья.

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

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

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

В обоих словах по букв, но в слове Коли при вычеркивании АТ и ТА получается одно и то же слово, а у Миши повторяющихся слов нет, так как нет двух одинаковых букв подряд и двух одинаковых через одну.

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

1.

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

2.

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

3.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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