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

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

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

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

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

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

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

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

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

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

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

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

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

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

• число  — проигрышное,
• число  — выигрышное,
• число  — проигрышное (так как единственный ход из него ведёт в выигрышное число ),
• число  — выигрышное (так как из него есть ход в проигрышное число ),

и так далее.

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

Докажем, что 2 и 17 — единственные выигрышные простые числа. Предположим, что это не так, и рассмотрим следующее выигрышное простое число В таком случае  — проигрышное чётное число, поэтому среди делителей не может быть простых чисел, кроме и Но тогда от него можно перейти либо к числу 34, либо к числу и выиграть.

Если составное число имеет простой делитель отличный от и то из него есть ход в проигрышное число то есть число является выигрышным. Остались числа вида

Нетрудно убедиться, что , ,  — выигрышные, а  — проигрышное, поэтому числа при  — выигрышные: от них можно перейти к

Число  — проигрышное, поэтому числа вида при  — выигрышные: от них можно перейти к

Число  — проигрышное, поэтому числа при  — выигрышные, так как от них можно перейти к

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

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

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

Цель первого игрока — добиться появления на доске фишки с весом 1 (т. е. фишки в первой клетке). Когда фишка сдвигается из клетки в клетку ее вес удваивается.

Игра в терминах весов выглядит следующим образом:

1.

Первый игрок разделяет множество всех фишек с общим весом на два подмножества с весами и где

2.

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

Докажем критерий выигрыша в обе стороны.

Случай 1: Докажем, что в этом случае первый игрок выигрывает. Стратегия первого игрока: на каждом ходу поддерживать инвариант — суммарный вес всех фишек на доске Для этого на каждом шаге он должен делить текущее множество фишек с общим весом на два подмножества, и так, чтобы их веса удовлетворяли условиям

______________________________________________________________________________________________________________________________________________________

Лемма. Любое мультимножество фишек с весами из набора

и суммарным весом можно разбить на два подмножества, вес каждого из которых не менее

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

Это противоречит условию, что исходная сумма Значит, после упрощения мы получим либо целую часть, либо достаточное количество дробей для разбиения.

_________________________________________________________________________________________________________________________________________________________________________________

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

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

Случай 2: Докажем, что в этом случае выигрывает второй игрок.

Стратегия второго игрока: после того как первый разделит фишки на группы и выбирать ту, у которой вес меньше. Пусть Тогда так как

Второй игрок оставляет группу и новый вес становится

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

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

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

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

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

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

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

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

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

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

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

Всего в круге имеется 100 пар соседних точек, и каждый игрок делает по 50 ходов. В итоге Боря добьётся того, что хотя бы 50 пар будут одноцветными, а Аня — что хотя бы 49 пар будут разноцветными. Однако количество разноцветных пар всегда чётно. Действительно, после окончания игры пройдём полный круг, начиная с какой-либо отмеченной точки (пусть для определённости с красной). Группы из идущих подряд красных и синих точек будут чередоваться: К—С—К—С—…—К, и значит, встретим пар разноцветных соседей вида К—С столько же, сколько пар вида С—К. Поэтому если пар разноцветных соседних точек не меньше 49, то их хотя бы 50.

Пусть в процессе было ходов.

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

количество клубней у (любого) мальчика перед первым ходом.

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

Поскольку все числа целые, получаем, что

при всех

Теперь можно получить оценки на числа действуя «с конца». Определим числа условиями

Докажем, что и индукцией по При неравенства очевидны; для перехода, чтобы доказать неравенство при некотором достаточно заметить, что

Итак, мы получаем, что Приведём таблицу первых значений чисел

Значит, из условия получаем, что

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

клубней, а перед любым предыдущим его ходом у него будет клубней при причём

Значит, этот ход удовлетворяет условию, и дети могут сделать 19 таких ходов.

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

Тогда отрезки и образуют треугольник: в сумме и как половина больше а неравенства и верны в силу равенства и

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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