Зворотна індукція та ігри

Ідея: Починайте з кінця

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

• Ходів немає: програш, коли виграє останній предмет
• Виграш: якийсь хід веде в програшну позицію
• Програш: кожен хід веде у виграшну позицію

Формула: Ігри на забирання

$n\mathrm{mod}(k+1)=0$

Якщо можна брати від 1 до k, програшні розміри кратні k + 1; на хід a відповідайте k + 1 − a.

Приклад: 21 сірник

$21$ сірник; за хід беруть $1$, $2$ або $3$; хто бере останній, виграє. Ходити першим? Скільки взяти?

1. Програшні розміри кратні $4$; на кожне $a$ відповідайте $4-a$
2. $21=5\times 4+1$, тож ходіть першим
3. Залиште $21-1=20$: візьміть $1$

Типова помилка: Не те правило виграшу

Брати ту саму таблицю, коли останній предмет програє. Програшні розміри зсуваються.

Натомість Тоді залишайте на $1$ більше за кратне $k+1$, а не кратне. Читайте правило виграшу двічі.

Ідея: Незвичні набори ходів

Таблиця працює для будь-яких ходів, навіть коли гарної формули немає.

• Ходи $1$, $3$, $4$: програшні розміри $0$, $2$, $7$, $9$, $14$, $16$
• Остача $0$ або $2$ від ділення на $7$, як $16=2\times 7+2$
• Період знаходьте, заповнюючи таблицю, а не вгадуючи

Швидка перевірка: Порахуйте програшні розміри

За ходів $1$, $3$ або $4$ скільки розмірів купки від $1$ до $30$ програшні для того, хто ходить?

Формула: Нім: двійкова сума

$a\oplus b\oplus c=0$

Додайте розміри купок у двійковому записі без перенесення; позиція програшна саме тоді, коли сума 0.

Приклад: Купки 3, 4 і 5

Нім із купками $3$, $4$, $5$: беріть будь-скільки з однієї купки; останній предмет виграє. Скільки взяти?

1. Двійково $011$, $100$, $101$: сума $010$
2. Переверніть середній біт у $3$: $001$, тобто $1$
3. Візьміть $3-1=2$ з першої купки

Ідея: Як сказати на співбесіді

Спершу назвіть програшні позиції, потім хід, що веде в одну з них.

• Ігри на забирання: назвіть період і правило відповіді
• Нім: проговоріть двійкові суми стовпчик за стовпчиком
• Саме на стовпчиках трапляються похибки