Matematyka.pl

\(\displaystyle{ A}\) i \(\displaystyle{ B }\) grają w grę, która polega na zdejmowaniu kamyków ze stosu; jest na nim \(\displaystyle{ n}\) kamieni, i w pierwszym ruchu (ruchy wykonywane są naprzemian) \(\displaystyle{ A}\) może zdjąć ich dowolną ilość (ale nie wszystkie). W każdym kolejnym ruchu można zdjąć ze stosu nie więcej niż przeciwnik zdjął w poprzednim ruchu. Grę wygrywa ten, który zdejmie wszystkie kamienie (opróżni stos).
Kto ma strategię wygrywającą ?

Wydaje mi się, że A przegrywa tylko wtedy, gdy \(\displaystyle{ n=2^k}\).

pesel pisze: ↑7 lis 2022, o 15:08 Wydaje mi się, że A przegrywa tylko wtedy, gdy \(\displaystyle{ n=2^k}\).

Istotnie, tak jest.
1) Gdy \(\displaystyle{ n=2m+1}\) to A w pierwszym ruchu zabiera 1 kamień zmuszając B do zbierania kamieni o numerach parzystych, samemu zbierając kamienie nieparzyste, w tym i ostatni.
2) Gdy \(\displaystyle{ n=4m+2}\) to A w pierwszym ruchu zabiera 2 kamienie. Jeśli B weźmie jeden kamień to A ma wygrywającą sytuację 1). Wzięcie dwóch kamieni daje sytuację 2) (aż do zabrania przez A ostatnich dwóch kamieni).
3) Gdy \(\displaystyle{ n=8m+4}\) to A w pierwszym ruchu zabiera 4 kamienie. Jeśli B weźmie jeden lub trzy kamienie to A ma wygrywającą sytuację 1). Wzięcie dwóch kamieni daje sytuację 2), a czterech sytuację 3) (aż do zabrania przez A ostatnich czterech kamieni).
...
...
l) Gdy \(\displaystyle{ n=2^lm+2^{l-1}}\) to A w pierwszym ruchu zabiera \(\displaystyle{ 2^{l-1}}\) kamienie. Jeśli B weźmie mniej niż \(\displaystyle{ 2^{l-1}}\) kamieni to A ma jedną z wygrywających sytuacji 1), 2) ..., l-1) . Wzięcie \(\displaystyle{ 2^{l-1}}\) kamieni daje sytuację l) (aż do zabrania przez A ostatnich \(\displaystyle{ 2^{l-1}}\) kamieni).

Dla \(\displaystyle{ n=2^k}\) wybranie przez A:
- nie mniej niż \(\displaystyle{ 2^{k-1}}\) kamieni pozwoli B na zabranie wszystkich pozostałych.
- mniej niż \(\displaystyle{ 2^{k-1}}\) pozwoli B na zastosowanie opisanej wcześniej strategii wygrywającej.