Wkuwać (gra)
Cram to gra matematyczna rozgrywana na kartce papieru milimetrowego . Jest to bezstronna wersja Domineering , a jedyna różnica w zasadach polega na tym, że gracze mogą układać swoje domino w dowolnej orientacji, ale skutkuje to zupełnie inną grą. Nazywano go wieloma nazwami, w tym „plugg” autorstwa Geoffreya Motta-Smitha oraz „kropki i pary”. Cram został spopularyzowany przez Martina Gardnera w Scientific American .
Zasady
Gra toczy się na kartce papieru milimetrowego, z wykreślonym dowolnym zestawem projektów. Najczęściej gra się na prostokątnej planszy, takiej jak kwadrat 6 × 6 lub szachownica , ale można ją również grać na całkowicie nieregularnym wielokącie lub cylindrycznej planszy.
Dwóch graczy ma kolekcję kostek domina , które po kolei umieszczają na siatce. Gracz może ułożyć kostkę domina poziomo lub pionowo. W przeciwieństwie do pokrewnej gry Domineering, możliwe ruchy są takie same dla obu graczy, a Cram jest wtedy grą bezstronną .
misère , przeciwnie, pierwszy gracz, który nie może się ruszyć, wygrywa .
Gra w symetrię
Zwycięska strategia dla zwykłego Crama jest prosta dla stołów parzystych i parzystych. W przypadku parzystych drugi gracz wygrywa dzięki grze symetrii . Oznacza to, że dla każdego ruchu Gracza 1, Gracz 2 ma odpowiedni ruch symetryczny wzdłuż osi poziomej i pionowej. W pewnym sensie gracz 2 „naśladuje” ruchy gracza 1. Jeśli gracz 2 zastosuje się do tej strategii, gracz 2 zawsze wykona ostatni ruch iw ten sposób wygra grę.
W przypadku parzystych po nieparzystych pierwszy gracz wygrywa dzięki podobnej grze symetrii. Gracz 1 umieszcza swoje pierwsze domino na środkowych dwóch polach planszy. Następnie gracz 2 wykonuje swój ruch, ale gracz 1 może później grać symetrycznie, zapewniając w ten sposób zwycięstwo graczowi 1.
Gra symetryczna jest strategią bezużyteczną w wersji misère , ponieważ w takim przypadku zapewniłaby tylko graczowi przegraną .
Wersja normalna
Wartość Grundy'ego
Ponieważ Cram jest grą bezstronną , twierdzenie Sprague-Grundy'ego wskazuje, że w normalnej wersji każda pozycja Crama jest równoważna stercie nim o danej wielkości, zwanej także wartością Grundy'ego . Niektóre wartości można znaleźć w Zwycięskich sposobach zabaw matematycznych , w szczególności na planszy 2 × n , której wartość wynosi 0, jeśli n jest parzyste, a 1, jeśli n jest nieparzyste.
Strategia symetrii implikuje, że tablice parzyste mają wartość Grundy'ego równą 0, ale w przypadku tablic parzystych oznacza to tylko wartość Grundy'ego większą lub równą 1.
| n × m | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|
| 4 | 0 | 2 | 0 | 3 | 0 | 1 |
| 5 | - | 0 | 2 | 1 | 1 | 1 |
| 6 | - | - | 0 | 5 | 0 | ≥1 |
| 7 | - | - | - | 1 | ≥1 | ? |
Znane wartości
W 2009 roku Martin Schneider obliczył wartości Grundy'ego do tablic 3 × 9, 4 × 5 i 5 × 7. W 2010 roku Julien Lemoine i Simon Viennot zastosowali w grze Cram algorytmy, które pierwotnie zostały opracowane dla gry Sprouts . Pozwoliło im to obliczyć wartości Grundy'ego do tablic 3 × 20, 4 × 9, 5 × 9, 6 × 7 i 7 × 7.
Sekwencja obecnie znanych wartości Grundy'ego dla 3 × n plansz, od n=1 do n=20 to: 1, 1, 0, 1, 1, 4, 1, 3, 1, 2, 0, 1, 2, 3 , 1, 4, 0, 1, 0, 2. Nie pokazuje żadnego widocznego wzoru.
Poniższa tabela wyszczególnia znane wyniki dla desek o obu wymiarach większych niż 3. Ponieważ wartość deski n × m jest taka sama jak wartość deski m × n , podajemy tylko górną część tabeli.
Wersja Misère
Wartość Misère Grundy
Wartość misère Grundy gry G jest zdefiniowana przez Conwaya w On Numbers and Games jako unikalna liczba n taka, że G + n jest wygraną drugiego gracza w grze misère. Nawet jeśli wygląda bardzo podobnie do zwykłej wartości Grundy'ego w normalnej grze, nie jest tak potężny. W szczególności nie jest możliwe wydedukowanie wartości misère Grundy sumy gier tylko z ich odpowiednich wartości misère Grundy.
| n × m | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|
| 4 | 0 | 0 | 0 | 1 | 1 | 1 |
| 5 | - | 2 | 1 | 1 | ? | ? |
| 6 | - | - | 1 | ? | ? | ? |
W 2009 roku Martin Schneider obliczył wartości misère grundy do tablicy 3 × 9, 4 × 6 i 5 × 5. W 2010 roku Julien Lemoine i Simon Viennot rozszerzyli te wyniki na plansze 3 × 15, 4 × 9 i 5 × 7, wraz z wartością planszy 6 × 6.
Sekwencja obecnie znanych wartości misère Grundy dla 3 × n plansz, od n=1 do n=15 to: 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1. Przypuszcza się, że ta sekwencja jest okresowa w okresie 3.
W sąsiedniej tabeli wyszczególniono znane wyniki misère dla desek o obu wymiarach większych niż 3.
- Berlekamp, Elwyn R .; Conway, John H .; Facet, Richard K. (2003). Zwycięskie sposoby na Twoje zabawy matematyczne . AK Peters spółka z ograniczoną odpowiedzialnością
- ^ Gardner, Martin (1974). „Gry matematyczne: Cram, crosscram i quadraphage: nowe gry o nieuchwytnych strategiach wygrywania”. Naukowy Amerykanin . 230 (2): 106–108. doi : 10.1038/scientificamerican0374-102 .
- Bibliografia Linki zewnętrzne _ _ _ _ _
- ^ Julien, Lemoine; Simon, Viennot (2010). „Nimbery są nieuniknione”. arXiv : 1011,5841 [ matematyka.CO ].
- ^ a b c „rekordy [SproutsWiki]” . sprouts.tuxfamily.org . Źródło 2023-02-12 .
- ^ John H., Conway (2000). O liczbach i grach . AK Peters, Ltd.