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

Фішки з обмеженими ходами

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

У купі $20$ фішок. $2$ гравці ходять по черзі, і за хід гравець забирає рівно $1$ , $3$ або $4$ фішки; хід, для якого фішок замало, заборонений. Хто не може походити, той програє, тож виграє той, хто забере останню фішку. Ви ходите першим, обидва гравці грають оптимально. Скільки фішок ви маєте забрати на першому ході, щоб гарантовано виграти?

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

Підказка

Позначте розміри купи, починаючи з $0$ , як виграшні чи програшні для того, хто ходить, і пошукайте повторюваний шаблон.

Розв’язок

Розмір $0$ програшний для того, хто ходить; розміри $1$ , $3$ і $4$ виграшні, бо можна забрати все, а розмір $2$ програшний, бо єдиний хід веде до $1$ .
Далі розміри $5$ і $6$ виграшні, бо з них можна перейти до $2$ , забравши $3$ або $4$ , а $7$ програшний, бо з нього ходи ведуть до $6$ , $4$ і $3$ .
Шаблон повторюється з періодом $7$ : програшні розміри мають остачу $0$ або $2$ від ділення на $7$ .
Із $20$ ходи ведуть до $19$ , $17$ і $16$ , і програшний лише $16$ , бо $16 = 2 \times 7 + 2$ .
Отже, спершу ви забираєте $4$ фішки.

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

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