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

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

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

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

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

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

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

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

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

Сначала приведём стратегию за Соню. Пока она не получила больше 299 монет, перед её ходом на доске остаётся хотя бы 101 монета. Разобьем доску на 100 квадратов Получается, что какие-то две монеты лежат в одном и том же квадрате Если эти две монеты соседние по стороне, то Соня надвигает одну на другую, и получает ещё одну монету. Если они стоят по диагонали, то Соня сдвигает одну из них в столбец к другой (здесь и далее столбец имеет длину 2, строка — длину 200). Теперь, какой бы ход ни сделала Даша, эти две монетки всё ещё будут соседними по стороне (либо одна будет снята и уйдёт в доход Сони), значит, своим следующим ходом Соня сможет получить ещё одну монетку. Таким образом, Соня всегда сможет увеличивать свой выигрыш, пока он меньше 300.

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

Назовём расположение монет на доске стабильным, если по одной красной монете лежит в столбцах а ещё одна располагается в одном из двух последних столбцов 199, 200. Легко видеть, что после любого хода из стабильной позиции две красные монеты не окажутся в одной клетке. Даша будет играть так, чтобы после каждого её хода получалась стабильная позиция. Если после хода Сони позиция осталась стабильной, то Даша двигает сотую красную фишку между двумя последними столбцами, так же Даша поступит и своим первым ходом. Если же после хода Сони позиция перестала быть стабильной, то Соня подвинула одну из красных монет из некоторого столбца в соседний столбец. Тогда Даша своим ходом вернёт её в столбец Таким образом, на доске всегда останется хотя бы 100 монет, и Соня заработает не более трёхсот рублей.

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

Пусть - итоговое шестизначное число. Пусть также и . Заметим, что если Боря своим третьим ходом поставит цифру из множества , Аня выиграет, поскольку полученное число будет делиться на 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 И: 5	=	;
Р: 3 И: 5	=	;
Р: 4 И: 5	=	;
Р: 5 И: 10	=	;
Р: 6 И: 9	=	;
Р: 7 И: 8	=	;
Р: 8 И: 7	=	;
Р: 9 И: 6	=	;
Р: 10 И: 5	=	.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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