Игры

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

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

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

Для любой прямой проходящей через точку обозначим через прямую, также проходящую через и перпендикулярную Одна из выигрышных стратегий Бориса: если Андрей провёл очередным своим ходом прямую то Борис проводит прямую

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

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

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

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

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

Разобьем числа от до на групшы: есть три числа, которые делятся на три числа, которые делятся на но не делятся на нечетных чисел, не делящихся на и четных чисел, не делящихся на Будем играть за Лену. Разобьем все числа в группах, кроме одного, на пары. Сами группы также разобьем на пары, и Если Катя ходит в новую группу, из которой девочки числа еще не стирали, то Лена стирает число из парной группы. Если же Катя ходит в группу, из которой числа уже стирали, то Лена стирает число из той же группы. Заметим, что ни из какой группы Катя не сможет забрать последнее число. Это значит, что если до хода Кати произведение оставшихся чисел делилось на то и после ее хода оно все еще делится на Поэтому Катя не может победить, значит, побеждает Лена, так как последний ход также делает она.

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

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

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

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

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

Будем действовать по следующему алгоритму, попутно объясняя, почему он сработает. Рассмотрим висячую вершину дерева и подвесим граф за нее. Сначала назовем только вершину

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

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

Назовем разветвлением вершину, степень которой больше 3.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Первым ходом Петя может, например, стереть все цифры Оставшиеся группы одинаковых цифр можно разбить на пары:

После этого Петя (относительно средней черты) повторяет ходы Васи: стирает цифры “парные” ходу Васи и в таком же количестве.

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

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