Игры → .03 Анализ позиций

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Разбив поле на четыре квадрата , получим, что для того, чтобы гарантированно ранить бублик, потребуется не менее 8 выстрелов.

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

Рассмотрим разность координат королей: обозначим их через и Заметим, что вначале Мы докажем, что в следующих позициях первый проигрывает, а во всех остальных выигрывает: a) и нечетно; б) и нечетно; в) и оба четны.

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

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

2) — мы просто уменьшаем на 1;

3) — аналогично предыдущему уменьшаем на 1 .

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

Рассмотрим ситуацию “за ход до проигрыша”, т. е. в которой невозможно сделать ход, чтобы не проиграть.

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

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

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

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

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

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

Если Полина возьмёт себе все черви, все тузы, всех королей и всех дам, то Василиса не сможет набрать очки на тузе, короле и даме червей, т. е. наберёт не больше очков.

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

Назовём типом столбца количество чёрных клеток в нём. Сначала Василиса рассматривает столбцы типа (если они есть). Каждый из них, очевидно, разбивается на две хорошие пары.

Далее Василиса рассматривает пары столбцов типа и Каждая такая пара, очевидно, разбивается на четыре хорошие пары клеток.

Далее Василиса рассматривает пары столбцов типа и Каждая такая пара тоже разбивается на четыре хорошие пары клеток (см. рисунок слева).

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

Так как то на всей доске останется не более трёх нехороших пар, т. е. Василиса «потеряет» не больше очков.

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

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

2) Аналогично, если то неравенство эквивалентно или же То есть нам так же нужно сравнить два числа: и при этом первая сестра знает, чему равно а вторая сестра знает, чему равно Пусть множество всех возможных значений это множество а множество всех возможных значений — это Сейчас Тогда

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

С каждым шагом будет уменьшать пересечение множеств и в два раза. Например, второй вопрос будет: «Верно ли, что » или «Верно ли, что » в зависимости от ответа на первый вопрос. Если на каком-то шаге то мы спрашиваем, верно ли, что (или в зависимости от того, кому задаем вопрос) больше, чем Таким образом, после второго вопроса в пересечении множеств будет и будет 250 элементов, после третьего вопроса — 175 элементов, после четвёртого — 88, и так далее. Получается, после десятого вопроса в пересечении будет всего один элемент. Пусть это будет число

При этом, после каждого вопроса уменьшается так же количество элементов в или в Пусть после десятого вопроса (или наоборот, все элементы множества не меньше а все элементы множества — небольше). Последние два вопроса будут: «Верно ли, что » или «Верно ли, что ». Если ответы на оба вопроса «да», то числа и равны, и загаданные сёстрами числа различаются ровно на 500. Если ответ на первый из этих вопросов «нет», то Аналогично, если ответ на второй вопрос «нет».

Так как 64 не делится на 3, то всю доску (64 клетки) нельзя покрыть не пересекающимися и не вылезающими за границу квадрата уголками из трёх клеток.

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

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

А в четвёртом квадрате любые три покрашенные клетки всегда можно покрыть одним уголком.

Назовем кусок шоколадки если его можно разрезать, и если нельзя. Изначально есть только один большой кусок, а в конце игры их Карлсон может играть так, чтобы четность количества больших кусков после его хода обязательно менялась: один большой кусок уничтожается ходом Малыша, после чего появляется от до новых больших кусков. Если количество новых больших кусков нечетно, то один точно есть и Карлсон его съест. Если же количество больших кусков четно, то есть хотя бы один малый и Карлсон съест именно малый кусок. Итак, число больших кусков после каждой пары полуходов меняет четность, а по окончании игры чётность чисел больших кусков должна измениться, значит, будет сделано нечётное количество ходов, т.е. Карлсон выиграет.

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

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