Cayley's mousetrap: Difference between revisions

Content deleted Content added

Inline

Latest revision as of 07:50, 18 November 2024

Mousetrap is the name of a game introduced by the English mathematician Arthur Cayley. In the game, cards numbered $1$ through $n$ ("say thirteen" in Cayley's original article) are shuffled to place them in some random permutation and are arranged in a circle with their faces up. Then, starting with the first card, the player begins counting $1,2,3,...$ and moving to the next card as the count is incremented. If at any point the player's current count matches the number on the card currently being pointed to, that card is removed from the circle and the player starts all over at $1$ on the next card. If the player ever removes all of the cards from the permutation in this manner, then the player wins. If the player reaches the count $n+1$ and cards still remain, then the game is lost.

In order for at least one card to be removed, the initial permutation of the cards must not be a derangement. However, this is not a sufficient condition for winning, because it does not take into account subsequent removals. The number of ways the cards can be arranged such that the entire game is won, for n = 1, 2, ..., are

1, 1, 2, 6, 15, 84, 330, 1812, 9978, 65503, ... (sequence A007709 in the OEIS).

For example with four cards, the probability of winning is 0.25, but this reduces as the number of cards increases, and with thirteen cards it is about 0.0046.

References

Cayley, Arthur (1878), "On the game of Mousetrap", Quarterly Journal of Pure and Applied Mathematics, 15: 8–10. University of Göttingen Göttinger Digitalisierungszentrum (GDZ) scan
Guy, Richard K.; Nowakowski, Richard J. (1993), "Mousetrap", in Miklos, D.; Sos, V. T.; Szonyi, T. (eds.), Combinatorics, Paul Erdős is Eighty, Bolyai Society Math. Studies, vol. 1, pp. 193–206, MR 1249712.
Mundfrom, Daniel J. (1994), "A problem in permutations: the game of 'Mousetrap'", European Journal of Combinatorics, 15 (6): 555–560, doi:10.1006/eujc.1994.1057, MR 1302079.
Spivey, Michael Z. (2009), "Staircase rook polynomials and Cayley's game of Mousetrap" (PDF), European Journal of Combinatorics, 30 (2): 532–539, doi:10.1016/j.ejc.2008.04.005, MR 2489284.

External links

Weisstein, Eric W. "Mousetrap". MathWorld.

This combinatorics-related article is a stub. You can help Wikipedia by expanding it.

@@ Line 1: / Line 1: @@
+{{Short description|Game in combinatorics}}
-'''Mousetrap''' is the name of a game introduced by the [[English people|English]] [[mathematician]] [[Arthur Cayley]].  In the game, cards numbered one through <math>n</math> are placed in some random [[permutation]].  Then, starting with the left-most card, the player begins counting "1, 2, 3, ...", moving to the next card as they increment their count.  If at any point the player's current count matches the number on the card currently being pointed to, that card is removed, and the player starts over at one on the next card.  When the player reaches the end of the cards (the right-most card), they simply wrap around to the left-most card and continue counting.  If the player ever removes all of the cards from the permutation in this manner, then the player wins.  If the player reaches <math>n</math> and cards still remain, then the cards win.
+{{No footnotes|date=November 2024}}
+'''Mousetrap''' is the name of a game introduced by the [[English people|English]] [[mathematician]] [[Arthur Cayley]].  In the game, cards numbered <math>1</math> through <math>n</math> ("say thirteen" in Cayley's original article) are shuffled to place them in some random [[permutation]] and are arranged in a circle with their faces up.  Then, starting with the first card, the player begins counting <math>1, 2, 3, ...</math> and moving to the next card as the count is incremented.  If at any point the player's current count matches the number on the card currently being pointed to, that card is removed from the circle and the player starts all over at <math>1</math> on the next card.  If the player ever removes all of the cards from the permutation in this manner, then the player wins.  If the player reaches the count <math>n+1</math> and cards still remain, then the game is lost.
+In order for at least one card to be removed, the initial permutation of the cards must not be a [[derangement]]. However, this is not a sufficient condition for winning, because it does not take into account subsequent removals. The number of ways the cards can be arranged such that the entire game is won,  for ''n'' = 1, 2, ..., are
+: 1, 1, 2, 6, 15, 84, 330, 1812, 9978, 65503, ... {{OEIS|A007709}}.
+For example with four cards, the probability of winning is 0.25, but this reduces as the number of cards increases, and with thirteen cards it is about 0.0046.
+==References==
+*{{citation
+ | last = Cayley | first = Arthur | author-link = Arthur Cayley
+ | journal = Quarterly Journal of Pure and Applied Mathematics
+ | pages = 8–10
+ | title = On the game of Mousetrap
+ | volume = 15
+ | year = 1878}}. [http://resolver.sub.uni-goettingen.de/purl?PPN600494829_0015 University of Göttingen Göttinger Digitalisierungszentrum (GDZ) scan]
+*{{citation
+ | last1 = Guy | first1 = Richard K. | author1-link = Richard K. Guy
+ | last2 = Nowakowski | first2 = Richard J.
+ | editor1-last = Miklos | editor1-first = D.
+ | editor2-last = Sos | editor2-first = V. T. | editor2-link = Vera T. Sós
+ | editor3-last = Szonyi | editor3-first = T.
+ | contribution = Mousetrap
+ | mr = 1249712
+ | pages = 193–206
+ | series = Bolyai Society Math. Studies
+ | title = Combinatorics, Paul Erdős is Eighty
+ | volume = 1
+ | year = 1993}}.
+*{{citation
+ | last = Mundfrom | first = Daniel J.
+ | doi = 10.1006/eujc.1994.1057
+ | issue = 6
+ | journal = [[European Journal of Combinatorics]]
+ | mr = 1302079
+ | pages = 555–560
+ | title = A problem in permutations: the game of 'Mousetrap'
+ | volume = 15
+ | year = 1994| doi-access = free
+ }}.
+*{{citation
+ | last = Spivey | first = Michael Z.
+ | doi = 10.1016/j.ejc.2008.04.005
+ | issue = 2
+ | journal = [[European Journal of Combinatorics]]
+ | mr = 2489284
+ | pages = 532–539
+ | title = Staircase rook polynomials and Cayley's game of Mousetrap
+ | url = https://mathcs.pugetsound.edu/~mspivey/MousetrapFinal2.pdf
+ | volume = 30
+ | year = 2009| doi-access = free
+ }}.
 == External links ==
-* [http://members.lycos.co.uk/rickycayley/CayleysMouseTrap.swf Cayley's MouseTrap]
 * {{MathWorld|urlname=Mousetrap|title=Mousetrap}}
-{{math-stub}}
 [[Category:Mathematical games]]
+{{combin-stub}}