Past na myši Cayleys - Cayleys mousetrap - Wikipedia

Past na myši je název hry představené Angličtina matematik Arthur Cayley. Ve hře byly karty očíslovány přes („řekněme třináct“ v původním článku Cayleyho) jsou zamíchány, aby byly zařazeny do nějakého náhodného výběru permutace a jsou uspořádány do kruhu lícem nahoru. Poté, počínaje první kartou, hráč začne počítat a přechod na další kartu s tím, jak se počet zvyšuje. Pokud se v kterémkoli okamžiku aktuální počet hráčů shoduje s číslem na právě poukazované kartě, je tato karta odstraněna z kruhu a hráč začíná znovu v na další kartě. Pokud hráč tímto způsobem z permutace odebere všechny karty, vyhrává. Pokud hráč dosáhne počtu a karty stále zůstávají, pak je hra ztracena.

Aby mohla být odstraněna alespoň jedna karta, nesmí být počáteční permutace karet a vykolejení. To však není dostatečná podmínka pro výhru, protože nebere v úvahu následné odebrání. Počet způsobů, jak lze karty uspořádat tak, aby byla vyhrána celá hra n = 1, 2, ..., jsou

1, 1, 2, 6, 15, 84, 330, 1812, 9978, 65503, ... (sekvence A007709 v OEIS ).

Reference

  • Cayley, Arthur (1878), „O hře Past na myši“, Quarterly Journal of Pure and Applied Mathematics, 15: 8–10. Skenování University of Göttingen Göttinger Digitalisierungszentrum (GDZ)
  • Guy, Richard K.; Nowakowski, Richard J. (1993), „Past na myši“, Miklos, D .; Sos, V. T.; Szonyi, T. (eds.), V kombinatorice je Paul Erdős osmdesátMatematika společnosti Bolyai. Studie, 1, s. 193–206, PAN  1249712.
  • Mundfrom, Daniel J. (1994), „Problém permutací: hra„ Past na myši “'", European Journal of Combinatorics, 15 (6): 555–560, doi:10.1006 / eujc.1994.1057, PAN  1302079.
  • Spivey, Michael Z. (2009), „Schodišťové věže polynomy a Cayleyova hra Past na myši“ (PDF), European Journal of Combinatorics, 30 (2): 532–539, doi:10.1016 / j.ejc.2008.04.005, PAN  2489284.

externí odkazy