Mousetrap is a permutation problem introduced by Cayley (1877). 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 .
At least one card is discarded iff the initial permutation has a fixed point. For , 2, ..., the numbers of such initial arrangements are 1,
1, 4, 15, 76, 455, ... (OEIS A002467).
The numbers of initial permutations for which all cards are discarded, for ,
2, ..., are 1, 1, 2, 6, 15, 84, 330, 1812, 9978, 65503, ... (OEIS A007709).
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, Hungary: 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, A002469/M3962,
and A007709 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, ..., the numbers of such initial arrangements are 1,
1, 4, 15, 76, 455, ... (OEIS A002467).
,
2, ..., are 1, 1, 2, 6, 15, 84, 330, 1812, 9978, 65503, ... (OEIS A007709).
