Игры

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

Ивану достаётся многочлен нечетной степени, поэтому он не может проиграть. Однако Кощей тоже не может проигрывать: для этого ему достаточно каждый раз выбирать положительный корень. Заметим, что свободный член всегда равен Легко проверить, что при такой стратегии Кощея Ивану будут доставаться многочлены нечетной степени с чередующимися знаками коэффициентов (старший - положительный), и поэтому у них есть лишь положительные корни; а Кощею будут доставаться многочлены четной степени с положительным старшим коэффициентом и свободным членом поэтому у них существует положительный корень

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

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

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

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

То есть

Иными словами, в интересующей нас клетке должно стоять число

Пользуясь этой формулой и значениями в клетках на краях, заполним всю табличку:

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

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

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

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

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

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

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

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

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

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

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

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

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

Назовём группой чисел размера группу чисел Пусть Петя сначала последовательно называет все числа из группы размера потом все числа из группы размера затем из группы размера и так дальше.

Покажем, что рано или поздно Петя проиграет. Любое число представимо в виде где — свободное от квадрата число или

Давайте поймём, как числа влияют на Если не делится на то после этих четырёх чисел не изменится. Если делится на но не делится на то оно тоже останется без изменений.

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

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

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

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

Разобьем все клетки на тройки следующим образом: в каждой строке разбиваем их на тройки с номерами Играем за Булата. Если Аскар ходит в некоторую тройку, то мы закрашиваем оставшиеся две клетки этой тройки.

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

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

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

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

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

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

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

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

Если бы количество камней было неограниченным, то Джон мог бы просто дополнять ходы Билла до четырёх и победить после своего -го хода. Однако заметим, что если Билл будет всегда выкладывать по одной монете, то Джону придётся выкладывать по три, а значит ему не хватит монет. Таким образом понимаем, что Джону необходимо сэкономить монеты. Если первым ходом Билл положит две или три монеты, то Джон положит две или одну и далее ему хватит монет для победы. Пусть Билл положил первым ходом одну монету, тогда Джон в ответ положит также одну. Далее возможны три варианта развития событий:

Если Билл снова положил одну монету, то Джон также кладёт одну, а далее дополняет до четырёх.

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

Если вторым ходом Билл выложит три монеты, то Джек также ответит тремя, а далее будет дополнять.

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

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

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

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

Пусть Аня возьмёт камень из второй кучки (число 1 является делителем числа 2021), то есть число камней станет равным. Дальше её стратегия очень проста — повторять ход Пети в другой кучке. Если Петя нашёл делитель числа и забрал камней из какой-то кучи, то Аня может забрать камней из другой кучки (в которой перед её ходом тоже будет камней), поскольку число является делителем текущего числа камней в кучке, откуда брал Петя. Раз игра когда-нибудь закончится, то Аня победит.

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

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

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

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

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

Приведём одну из возможных выигрышных стратегий за Пашу.

Пронумеруем шарики подряд числами от 1 до 2021. Первым ходом покрасим в красный цвет шарик номер 1011 (средний во всём ряду). Пусть Вова, не умаляя общности, свой ход сделал в левую половину. Тогда вторым ходом Паша красит в жёлтый цвет шарик с номером 1014.

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

Осталось заметить, что Паша может заставить Вову сделать ход между покрашенными первыми двумя ходами шариками. Сам Паша туда ходить не будет, и после покраски всех остальных шариков по чётности будет ход Вовы. Значит, Паша победит.

Разобьем клетки доски на пары-доминошки следующим образом:

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