Стратегии дополнения

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

Докажем, что данная стратегия является выигрышной. После каждой пары ходов Пети и Васи фишка будет передвинута на 3 клетки, следовательно, после хода Васи фишка будет передвинута на клеток. Наконец, после 33 хода фишка будет передвинута на 99 клеток и окажется в последней.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть — вершина пирамиды, — её основание. Разобьём все рёбра пирамиды на пары смежных, одно из которых боковое, а другое лежит в основании:

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

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

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

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

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

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

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

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

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