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

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

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

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

задан 13 Янв 1:21

10|600 символов нужно символов осталось
1

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

Я исследовал такую игру целиком для общего случая. Это делается при помощи функции Гранди. В похожих задачах эта функция может принимать весьма сложный вид, но здесь закономерность оказалась простой. Для "линейного" варианта с n лепестками, если можно вырывать или один откуда угодно, или два с краю, получается ответ G(n)= n mod 4 (остаток от деления на 4). То есть в такой игре начинающий проигрывает тогда и только тогда, когда число лепестков кратно 4. Это утверждение несложно проверяется по индукции.

Соответственно, если у круглой ромашки был 4n+1 лепесток, то выиграет первая девочка, а не вторая. Это легко проверить вручную для ромашки из 5 лепестков.

ссылка

отвечен 13 Янв 5:15

@falcao, большое спасибо! Источник головоломки - вот: http://puzzle-ru.blogspot.com/2014/08/blog-post_27.html Причём сами они в качестве «источника источника» указывают Энциклопедический словарь юного математика. В указанном словаре мне не удалось найти данную головоломку, зато теперь у меня есть этот замечательный словарь! Получилось как у Серендипа, который искал булавку, а нашёл золотой :)

(13 Янв 11:52) Казвертеночка

@falcao, на соседнем форуме утверждают, что вторая девочка выигрывает в любом случае: https://dxdy.ru/topic132401.html В чём они неправы?

(13 Янв 16:59) Казвертеночка
1

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

(13 Янв 17:23) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×1,128
×94
×78
×4
×3

задан
13 Янв 1:21

показан
178 раз

обновлен
13 Янв 17:23

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru