Игра с монетами

[Deathrose]

В ряд выложено $7000$ монет. Двое игроков по очереди выбирают число $k$ от 1 и не большее $100$ и переворачивают некоторый последовательный блок из $k$ монет. Игрок проигрывает, если после его хода конфигурация орлов и решек совпала с ранее встречавшейся. Кто из игроков может победить независимо от действий противника?

[Geen]

Deathrose в сообщении #1644109 писал(а):

Игрок проигрывает, если после его хода конфигурация орлов и решек совпала с ранее встречавшейся.

На всех 7000-ах монет?

[Deathrose]

Geen в сообщении #1644116 писал(а):

Deathrose в сообщении #1644109 писал(а):

Игрок проигрывает, если после его хода конфигурация орлов и решек совпала с ранее встречавшейся.

На всех 7000-ах монет?

Да, конфигурации всех $7000$ монет.

wrest, а чего сообщение-то удалили свое? Так уверенно писали, аж раздавить уверенностью могли.

[wrest]

Deathrose в сообщении #1644148 писал(а):

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

Уверенность испарилась

[Geen]

Deathrose в сообщении #1644109 писал(а):

Кто из игроков может победить независимо от действий противника?

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

[lel0lel]

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

[Deathrose]

lel0lel в сообщении #1644173 писал(а):

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

Доказывать нужно, и что вообще вторая фраза означает? Какая у вас стратегия? (просто всегда крутить одну и ту же монету - так это очевидно к проигрышу приведет)
На таком уровне обсуждать любые задачи трудно и не особо осмысленно.

[sergey zhukov]

Deathrose
Ну почему же? Можно разделить множество монет на первую и все остальные. Комбинации всех остальных монет сопоставим числам, а первая монета будет обозначать знак числа (начинаем с плюс нуля). Тогда игра может выглядеть так (первый игрок первым ходом меняет знак):
+0
-0
-10
+10
+57
-57
-81
+81
...
Как видно, второй игрок перебирает комбинации, а первый "столбит" положительный и отрицательный вариант. Второй не может уже их повторить и вынужден перебирать разные комбинации. Второй игрок может даже переворачивать за свой ход в одном блоке и первую монету включительно, но тогда в этой последовательности просто в некоторых местах плюс и минус у одного и того же числа поменяются местами. Например, это могло бы выглядеть так:

+57
-57
+81
-81
...

[lel0lel]

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

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

[Deathrose]

lel0lel
Да, действительно, такое рассуждение решает.
Была старая задача про такую же игру, но в которой каждый переворачивает одну монету. В ней доказать, что побеждает первый несложно - всего есть $2^n$ конфигураций монет и после каждого хода первого остается чётное число доступных (т.к. исключена первая конфигурация). Поэтому, проиграет второй игрок. Здесь по сути получается то же самое, но увидеть это было ощутимо сложнее.

[wrest]

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

[wrest]

Конечное и четное количес во возможных комбинаций тут очевидно, конечно. Меня смутило что на каждом ходу количество возможных далее ходов равно количеству монет (если ходить одной) или другому но тоже небольшому, если ходить блоками монет, соответсвенно нельзя произвольно создать любую комбинацию.
Например при ходе одной монетой в ряду из трёх, из комбинации 010 можно получить только комбинации 110 000 и 011 а не любую 000...111
Ну и дальше я не додумал...