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

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

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

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

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

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

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

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

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

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

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

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

Сначала покажем, что при емкости вёдер Кащей сможет добиться того, что ведро будет переполнено. Если то Кощею достаточно литр поместить в одно какое-то ведро.

Иначе пусть где и пусть ведра пронумерованы по кругу: соответственно. Тогда пусть Кощей наливает в первое ведро а в третье литров воды.

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

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

Решение 1. Проанализируем выигрышные и проигрышные позиции. Понятно, что все числа от 1 до 10 — выигрышные.

Число 11 — проигрышное, так как из нее можно попасть только в выигрышные позиции 1–10. Позиции 12–21 — выигрышные, ведь из них можно попасть в 11. Число 22 — проигрышное, и так далее.

Легко видеть, что все позиции, кратные 11, являются проигрышными, а остальные — выигрышными.

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

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

Другой подход — дополнение хода соперника до определенного значения.

Решение 2. При количестве спичек, кратном 11, будем играть за второго игрока, дополняя количество спичек, взятых на предыдущем ходу первым игроком, до 11. Другими словами, если первый игрок только что взял спичек, то мы берем . Сразу отметим, что количество спичек, которое мы должны брать в ответ на ход первого, также от 1 до 10, то есть с этим проблем не возникает. Кроме того, после нашего хода количество спичек после пары ходов — соперника и нашего — кратно 11, поэтому последнюю спичку заберет именно второй игрок.

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

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

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

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

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

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

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

Р: 2 И: 5	=	;
Р: 3 И: 5	=	;
Р: 4 И: 5	=	;
Р: 5 И: 10	=	;
Р: 6 И: 9	=	;
Р: 7 И: 8	=	;
Р: 8 И: 7	=	;
Р: 9 И: 6	=	;
Р: 10 И: 5	=	.

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

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

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

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

Далее будем красить какие угодно шары, кроме двух особенных, до тех пор, пока Вова не покрасит один из особенных шаров. Такой момент обязательно будет, так как после первых трех ходов осталось 2016 обычных шаров и 2 особенных (и сейчас ход второго). Когда игроки будут красить 2016 обычных шаров, то у Паши всегда будет ход после Вовы (из-за четности числа 2016).

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

Следовательно, Паша имеет выигрышную стратегию.

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

Если то второй игрок, очевидно, побеждает. Если то побеждает первый игрок, забирая первым ходом 1 камень. Если то побеждает второй игрок: если первый берет 1 камень, то второй возьмет последний камень, а если первый игрок первым ходом берет 2 или 3 камня, то второй игрок первым своим ходом забирает остальные камни.

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

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

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

Заметим, для начала, что если на доске чётное количество чисел, то ходит Марина, а если нечётное — Саша.

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

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

Докажем теперь, что если или то выигрывает Марина. Заметим, что если в какой-то момент на доске окажутся одни нули, то Марина выигрывает. Тогда при Марина точно уже выиграет.

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

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

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

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

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

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

Легко понять, что фишка всегда сможет посетить клеток. Достаточно поместить ее в вершину с наименьшем номером среди некоторых последовательных вершин, а затем пропрыгать по всем этим вершинам в порядке возрастания их номеров.

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

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