TOPICS
Search

Mousetrap


A permutation problem invented by Cayley. Let the numbers 1, 2, ..., n be written on a set of cards, and shuffle this deck of cards. Now, start counting using the top card. If the card chosen does not equal the count, move it to the bottom of the deck and continue counting forward. If the card chosen does equal the count, discard the chosen card and begin counting again at 1. The game is won if all cards are discarded, and lost if the count reaches n+1.

The number of ways the cards can be arranged such that at least one card is in the proper place for n=1, 2, ... are 1, 1, 4, 15, 76, 455, ... (OEIS A002467).


Explore with Wolfram|Alpha

References

Cayley, A. "A Problem in Permutations." Quart. Math. J. 1, 79, 1857.Cayley, A. "On the Game of Mousetrap." Quart. J. Pure Appl. Math. 15, 8-10, 1877.Cayley, A. "A Problem on Arrangements." Proc. Roy. Soc. Edinburgh 9, 338-342, 1878.Cayley, A. "Note on Mr. Muir's Solution of a Problem of Arrangement." Proc. Roy. Soc. Edinburgh 9, 388-391, 1878.Guy, R. K. "Mousetrap." §E37 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 237-238, 1994.Guy, R. K. and Nowakowski, R. J. "Mousetrap." In Combinatorics, Paul Erdős is Eighty, Vol. 1 (Ed. D. Miklós, V. T. Sós, and T. Szőnyi). Budapest: János Bolyai Mathematical Society, pp. 193-206, 1993.Guy, R. K. and Nowakowski, R. J. "Monthly Unsolved Problems, 1696-1995." Amer. Math. Monthly 102, 921-926, 1995.Muir, T. "On Professor Tait's Problem of Arrangement." Proc. Roy. Soc. Edinburgh 9, 382-387, 1878.Muir, T. "Additional Note on a Problem of Arrangement." Proc. Roy. Soc. Edinburgh 11, 187-190, 1882.Mundfrom, D. J. "A Problem in Permutations: The Game of 'Mousetrap.' " European J. Combin. 15, 555-560, 1994.Sloane, N. J. A. Sequences A002467/M3507, A002468/M2945, and A002469/M3962 in "The On-Line Encyclopedia of Integer Sequences."Steen, A. "Some Formulae Respecting the Game of Mousetrap." Quart. J. Pure Appl. Math. 15, 230-241, 1878.Tait, P. G. Scientific Papers, Vol. 1. Cambridge, England: University Press, p. 287, 1898.

Referenced on Wolfram|Alpha

Mousetrap

Cite this as:

Weisstein, Eric W. "Mousetrap." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Mousetrap.html

Subject classifications