W lewym dolnym rogu planszy \(\displaystyle{ m \times n}\) stoi pionek. W każdym ruchu może być on przesunięty o dowolną liczbę pól: w górę lub w prawo. Wygrywa ten, kto postawi figurę w prawym górnym rogu. Rozstrzygnąć dla jakich wartości \(\displaystyle{ (m, n)}\) pierwszy gracz ma strategię wygrywającą.
Jaka jest jego strategia
Rozważyć przestrzenna (sześcienną ) wersję gry.
Pionek na planszy
- mol_ksiazkowy
- Użytkownik
- Posty: 11503
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3163 razy
- Pomógł: 749 razy
-
- Administrator
- Posty: 34370
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5208 razy
Re: Pionek na planszy
Bez straty ogólności możemy założyć, że \(\displaystyle{ m\ge n.}\) Jeżeli graczowi pierwszemu uda się postawić pionek na polu o współrzędnych \(\displaystyle{ (m-1,n-1),}\) to wygra, bo gracz drugi musi przesunąć pionek na skrajny rząd bądź skrajną kolumnę. Zatem problem redukuje się indukcyjnie do wygranej w grze \(\displaystyle{ (m-n+1)\times1}\), a tę grę oczywiście gracz pierwszy wygrywa w jednym ruchu, o ile może się ruszyć.
Wobec tego gracz pierwszy ma strategię wygrywającą, gdy \(\displaystyle{ m>n}\) i polega ona na ustawieniu pionka na polu o współrzędnych \(\displaystyle{ (m-n+1,1)}\), a w kolejnych ruchach na kopiowaniu ruchów przeciwnika po drugiej współrzędnej. W przypadku \(\displaystyle{ m=n}\) strategię wygrywająca ma gracz drugi i polega ona na wracaniu w swoim ruchu na główną przekątną.
JK
Wobec tego gracz pierwszy ma strategię wygrywającą, gdy \(\displaystyle{ m>n}\) i polega ona na ustawieniu pionka na polu o współrzędnych \(\displaystyle{ (m-n+1,1)}\), a w kolejnych ruchach na kopiowaniu ruchów przeciwnika po drugiej współrzędnej. W przypadku \(\displaystyle{ m=n}\) strategię wygrywająca ma gracz drugi i polega ona na wracaniu w swoim ruchu na główną przekątną.
JK