A permutation problem invented by Cayley. Let the numbers 1, 2, ...,
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 .
The number of ways the cards can be arranged such that at least one card is in the proper place for ,
2, ... are 1, 1, 4, 15, 76, 455, ... (OEIS A002467).
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. Edinburgh9, 338-342,
1878.Cayley, A. "Note on Mr. Muir's Solution of a Problem
of Arrangement." Proc. Roy. Soc. Edinburgh9, 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. Monthly102,
921-926, 1995.Muir, T. "On Professor Tait's Problem of Arrangement."
Proc. Roy. Soc. Edinburgh9, 382-387, 1878.Muir, T. "Additional
Note on a Problem of Arrangement." Proc. Roy. Soc. Edinburgh11,
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.
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 
.
,
2, ... are 1, 1, 4, 15, 76, 455, ... (OEIS A002467).
