Навчання / Бібліотека / Головоломки

Яких початків уникати

ГоловоломкиСереднє

У грі для $2$ гравців купа спочатку містить $n$ намистин. Гравці ходять по черзі, і кожен хід забирає рівно $2$ або рівно $5$ намистин; хід, для якого намистин замало, заборонений. Гравець, який не може походити, програє. Обидва гравці грають оптимально. Для скількох початкових значень $n$ від $1$ до $50$ виграє другий гравець?

Для перевірки відповіді потрібен JavaScript. Підказка й розв’язок відкриваються і без нього.

Підказка

Класифікуйте малі купи як виграшні чи програшні для того, хто ходить, доки шаблон не почне повторюватися.

Розв’язок

Купи з $0$ і $1$ намистин програшні для того, хто ходить, бо ходу немає.
Купи з $2$ і $3$ намистин виграшні, бо можна перейти до $0$ або $1$ , купа з $4$ програшна, бо з неї можна дійти лише до $2$ , а купи з $5$ і $6$ виграшні, бо ведуть до $0$ або $4$ .
Далі шаблон повторюється з періодом $7$ , тож програшні купи мають остачу $0$ , $1$ або $4$ від ділення на $7$ .
Від $1$ до $50$ є $7$ значень з остачею $0$ , $8$ з остачею $1$ і $7$ з остачею $4$ .
Отже, другий гравець виграє для $7 + 8 + 7 = 22$ початкових значень, і відповідь $22$ .

Відповідь: $22$

Наступна задача Назад до бібліотеки