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
More things to try:
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
MousetrapCite this as:
Weisstein, Eric W. "Mousetrap." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Mousetrap.html