Pułapka na myszy Cayleya
Pułapka na myszy to nazwa gry wprowadzonej przez angielskiego matematyka Arthura Cayleya . W grze karty ponumerowane do („powiedzmy trzynaście” w oryginalnym artykule Cayleya) są tasowane w celu umieszczenia ich w jakiejś losowej permutacji i układane w okrąg awersami do góry. Następnie, zaczynając od pierwszej karty, gracz zaczyna liczyć i przejście do następnej karty w miarę zwiększania liczby. Jeśli w dowolnym momencie aktualna gracza odpowiada liczbie na aktualnie wskazywanej karcie, ta karta jest usuwana z koła, a gracz zaczyna wszystko od nowa następnej karcie. Jeśli gracz kiedykolwiek usunie w ten sposób wszystkie karty z permutacji, wygrywa. Jeśli gracz osiągnie liczbę, karty nadal pozostaną, gra
Aby usunąć co najmniej jedną kartę, początkowa permutacja kart nie może być zaburzeniem . Nie jest to jednak wystarczający warunek wygranej, ponieważ nie uwzględnia kolejnych usunięć. Liczba sposobów ułożenia kart w taki sposób, że cała gra jest wygrana, dla n = 1, 2, ..., wynosi
Na przykład przy czterech kartach prawdopodobieństwo wygranej wynosi 0,25, ale zmniejsza się wraz ze wzrostem liczby kart, a przy trzynastu kartach wynosi około 0,0046.
- Cayley, Arthur (1878), „O grze w pułapkę na myszy”, Quarterly Journal of Pure and Applied Mathematics , 15 : 8–10 . Skan Uniwersytetu w Getyndze Göttinger Digitalisierungszentrum (GDZ).
- Facet, Richard K .; Nowakowski, Richard J. (1993), "Pułapka na myszy", w: Miklos, D.; Sos, VT ; Szonyi, T. (red.), Kombinatoryka, Paul Erdős is Eighty , Bolyai Society Math. Studia, tom. 1, s. 193–206, MR 1249712 .
- Mundfrom, Daniel J. (1994), „Problem w permutacjach: gra w pułapkę na myszy” , European Journal of Combinatorics , 15 (6): 555–560, doi : 10.1006/eujc.1994.1057 , MR 1302079 .
- Spivey, Michael Z. (2009), „Wielomiany wieżowe schodów i gra Cayleya w pułapkę na myszy” (PDF) , European Journal of Combinatorics , 30 (2): 532–539, doi : 10.1016/j.ejc.2008.04.005 , MR 2489284 .
Linki zewnętrzne