Две девочки играют в такую игру: они по очереди отрывают лепестки у ромашки. За один ход можно оторвать либо один лепесток, либо два соседних (с самого края). Выигрывает девочка, сорвавшая последний лепесток. Докажите, что вторая девочка всегда может выиграть (у ромашки больше двух лепестков).
Своим первым ходом вторая девочка должна разбить венчик цветка на две симметричные половины, а затем отрывать лепестки симметрично тому, что делает первая девочка.
1 комментарий:
Здравствуйте!
В решении этой головоломки у вас ошибка.
Мне головоломка сразу же показалась подозрительной и я отправил её условие на форум, где вскоре получил вот такой ответ:
«Здесь какое-то слишком явное несоответствие -- может, пропустили условие, что изначальное число лепестков было чётным? В этом случае "края" нет, и первая отрывает один лепесток. Тогда их число становится нечётным, и вторая может вырвать средний. Тривиален также вариант, когда два лепестка можно вырывать подряд, но не обязательно с краю.
Я исследовал такую игру целиком для общего случая. Это делается при помощи функции Гранди. В похожих задачах эта функция может принимать весьма сложный вид, но здесь закономерность оказалась простой. Для "линейного" варианта с n лепестками, если можно вырывать или один откуда угодно, или два с краю, получается ответ G(n)= n mod 4 (остаток от деления на 4). То есть в такой игре начинающий проигрывает тогда и только тогда, когда число лепестков кратно 4. Это утверждение несложно проверяется по индукции.
Соответственно, если у круглой ромашки был 4n+1 лепесток, то выиграет первая девочка, а не вторая. Это легко проверить вручную для ромашки из 5 лепестков.»
С уважением,
Ян Альбертович Дененберг,
Назарет
Отправить комментарий