Игра «Лепестки ромашки» [Головоломка]

[Ktina]

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

Ответ на эту головоломку показался мне странным, он звучит следующим образом:

Цитата:

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

А как быть, если у ромашки изначально было чётное число лепестков, а первая девочка своим первым ходом взяла один лепесток? Как тогда вторая сможет разбить нечётку пополам?

[waxtep]

Оторвать один лепесток напротив оторванного

[Ktina]

waxtep
А если лепестков, например, пять?

[GAA]

Если лепестков 5 и первый оторвал 1, то второй отрывает два, напротив этого оторванного (остаются 2 не смежных лепестка). Второй игрок выигрывает.
Если лепестков 5 и первый оторвал 2, то второй отрывает один напротив этих двух оторванных (и остаются, как и в предыдущем случае, два лепестка).

Если лепестков 6 и первый отрывает 1, то и второй отрывает один, напротив этого оторванного. Если лепестков 6 и первый отрывает 2, то и второй отрывает два напротив этого оторванного оторванных. Выигрывает второй.

…

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

Следовательно, второй игрок гарантированно выигрывает.

Как бы интуитивно очевидно. Нужно какое-то формальное обоснование?

[Ktina]

GAA

Цитата:

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

[waxtep]

Ktina в сообщении #1368141 писал(а):

За один ход можно оторвать либо один лепесток, либо два соседних (с самого края)

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

[PETIKANTROP]

Из условия следует:
1. Девочка №1 первым ходом может сорвать только 1 лепесток, т.к. у целого венчика нет края!
2. Расчленять цветок каждый раз можно только с самого края - либо по часовой, либо против.

Ktina в сообщении #1368327 писал(а):

Там при пяти лепестках выигрывает первая девочка, что легко проверить перебором.

Почему же? Первая девочка рвет 1 лепесток. Вторая рвет тоже 1. Остается 3 -> выигрывает вторая девочка!
Для семицветика такого исхода уже не предвидится.

[waxtep]

PETIKANTROP в сообщении #1368351 писал(а):

Остается 3 -> выигрывает вторая девочка!

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

[PETIKANTROP]

waxtep в сообщении #1368357 писал(а):

один лепесток первая девочка может выдернуть и из середины этих трех

не может

PETIKANTROP в сообщении #1368351 писал(а):

2. Расчленять цветок каждый раз можно только с самого края

[waxtep]

PETIKANTROP, я предположил, что оговорка "с самого края" относится только к отрыванию двух лепестков, а один - дери откуда хочу!
Вообще же, задача определения у ромашки края может быть довольно коварной:

[GAA]

Ktina в сообщении #1368327 писал(а):

GAA
….

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

[waxtep]

Исходник в Кванте:

Цитата:

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

В отличие от края, начало у ромашки понятно где

[Ktina]

GAA
Это не мне спасибо, а Falcao.

[dimkadimon]

Это очень известная игра Ним:
https://ru.wikipedia.org/wiki/%D0%9D%D0 ... 1%80%D0%B0)