RECENT IMPROVEMENTS!!!
MODULAR MOUSETRAP 14x1:
TOTAL NUMBER OF DIFFERENT DECKS: 14! = 87.178.291.200
TOTAL NUMBER OF REFORMED DECKS (INCLUDING CYCLES): 21.487.935.690
FREQUENCY OF WINNING DECKS: 0.2465
TOTAL COST OF FILE STORAGE: 1600 GB
MAX
lenght k of reformed decks: 19MAX lenght k of a trajectory: 25
MAX lenght k of a pre-period: 24
MAX lenght k of a cycle: k = 2
number of different 1-cycles: 1
MODULAR MOUSETRAP 19x1:
STUDYING ONLY PARTIALLY (19! ≈ 121.645.100.400.000.000 DECKS!!!!!) THIS CASE, I FOUND TWO 14931-CYCLES
a) 1 5 14 11 7 6 2 12 15 8 9 18 16 3 4 10 13 19 17
b) 1 3 12 13 2 11 14 6 4 5 7 8 9 10 15 16 17 18 19
AND ONE 521339-TRAJECTORY:
1 2 12 14 3 6 10 16 18 9 15 19 13 7 17 11 5 4 8
WHICH IS FORMED BY A 521338-PRECYCLE AND THE TRIVIAL 1-CYCLE.
SEE BELOW FOR THE EXPLANATION OF THE GAME.
In 1857 Cayley [3] proposed a game called Mousetrap, played with a deck containing only one suit; here we report the description given in [5, p. 237]:
"Suppose that the numbers 1; 2; ... ; n are written on cards, one to a card. After shuffling (permuting) the cards, start counting the deck from the top card down. If the number on the card does not equal the count, transfer the card to the bottom of the deck and continue counting. If the two are equal then set the card aside and start counting again from "one". The game is won if all the cards have been set aside, but lost if the count reaches n + 1."
Cayley posed the fundamental question [4]:
"Find all the different arrangements of the cards, and inquire how many of these there are in which all or any given smaller number of the cards will be thrown out; and (in the several cases) in what orders the cards are thrown out."
Relatively few authors (in chronological order: [4], [11], [5], [7], [9], [6], [8], [10]) have studied the problem, arriving, only recently [6, 9, 10], at partial results.
In [5, p. 238], [6] and [7] Guy and Nowakowski consider another version of the game, called Modular Mousetrap, where, instead of stopping the game when no matching happens counting up to n, we start our counting again from "one", arriving either to set aside every card or at a loop where no cards can be set aside anymore. Obviously, in this game, if n is prime, we have only two possibilities: either derangement, where no coincidences occur, or winning deck. Guy and Nowakowski study completely only a small number of cases (n < 6), while in the case n = 6 they consider only decks starting with an "ace".
In the paper An "eulerian" approach to a class of matching problems [1] I introduced a new algorithm, which allows us to obtain many further results, in particular for what concerns the number of winning decks, and to answer some open questions. The study was extended to "multisuit" Mousetrap: n = m x s, where s is the number of suits and m is the maximal value of the cards.
In the original preprint you can find an historical introduction to the games Treize, Mousetrap and He Loves Me, He Loves Me Not (HLMN), which are strictly connected. In a more recent version, submitted for publication, you can find the most advanced results.
In their papers devoted to Mousetrap and Modular Mousetrap, Guy and Nowakowski first proposed to study the so-called reformed decks (or permutations): "consider a permutation for which every number is set aside. The list of numbers in the order that they were set aside is another permutation. Any permutation obtained in this way we call a reformed permutation. Characterize the reformed permutations."
In other words, when a deck wins at Mousetrap and Modular Mousetrap, it generates a new deck, which is called reformed deck. We can play again with this new deck, in order to check if it will win again.
When we can repeat this operation k times, we will define k-times reformable deck the original deck and k-reformed deck the permutation obtained in the k-th reformation.
Guy and Nowakowski posed the following questions:
1) characterize the reformed permutations;
2) for a given n, what is the longest sequence of reformed
permutations?
3) are there sequences of arbitrary length? are there any non
trivial cycles, i.e., cycles other than 1 -> 1 -> 1 ...
and 1 2 -> 1 2 -> 1 2 ... ?
4) in Modular Mousetrap are there k-cycles for every
k? what is the least value of n which yields a k-cycle?
For what concerns reformed decks, we
will need some terminology, in order to distinguish the different
situations we will deal with.
We will divide the reformed decks into two different categories:
i) k-reformed decks;
ii) k-cycles, i.e., decks which are reformed k times
and such that the k-th deck coincides with one of the previous
reformations.
If the k-th reformation coincides the h-th reformation (0 < h < k), we will divide the total k-cycle into two parts:
i) a h-pre-loop, where there is
a sequence of h reformations;
ii) a (k - h)-loop, starting from the h-th reformation
and stopping at the k-th reformation, which coincides with
the h-th one.
In the paper Reformed permutations in Mousetrap and its generalizations [2], I obtained many results, in particular for what concerns Modular Mousetrap, by means of the "eulerian" (or backward) technique, introduced in [1]. I also extended the analysis to the case of more than one suit. In the most recent version of the paper I show the number of k-reformed decks for many cases for Mousetrap and Modular Mousetrap and I give (though partial) answers to questions 1) -> 4).
_________________________________________________________________________________________________________________________
_________________________________________________________________________________________________________________________
The most interesting and intriguing results were obtained playing Modular Mousetrap, when n is a prime number.
For m = n = 11, I found six 203-cycles, obtained starting from the decks
1 11 5 8 2 6 9 4 7 10 3 ; 1 11 5 8 2 6 9 10 7 4 3 ; 1 11 5 9 2 6 10 8 7 4 3 ; 1 11 5 8 2 6 4 9 7 10 3 ; 1 11 5 8 2 6 4 9 10 3 7 ; 1 11 5 9 2 6 8 10 7 4 3 .
For example, the deck
1 11 5 8 2 6 9 4 7 10 3 ,
after 137 reformations, enters in a 66-loop, because the 203-th reformed deck ( 1 2 3 4 7 5 6 8 9 10 11) is identical to the 137-th deck.
File 203_cycles_11_1.txt contains the sequence of reformed decks starting from 1 11 5 8 2 6 9 4 7 10 3.
m = 13 has given, up to now, the longest reformation. I have found eleven 51-reformable decks. One of them is
6 2 5 11 1 8 13 12 7 9 10 3 4 .
File 51_reformed_13_1.txt contains the sequence of reformed decks starting from 6 2 5 11 1 8 13 12 7 9 10 3 4 .
Long cycles were discovered for m = 13, too: the deck
1 2 6 13 3 9 5 12 10 8 7 11 4
is characterized by a 840-cycle; after a 839-pre-loop we obtain the deck
1 2 3 4 5 6 7 8 9 10 11 12 13
and the cycle ends in a 1-loop.
File PRE_LOOP_839_13_1.txt contains the sequence of reformed decks starting from 1 2 6 13 3 9 5 12 10 8 7 11 4
Curiously, for m = 11 the decks
gave only 1; 2; 3; 4; 14; 15 and 66-loops. The number of decks
entering in a 66-loop is very high: 1,701,937. For m =
13 I found only 1; 2; 3; 6; 7 and 12-loops.
Since I expect to achieve many more interesting results whenever
n is prime, I have also examined the first 54 million reformed
decks for s = 1 and m = 17 and the first 332 million
reformed decks for s = 1 and m = 19.
We can understand the richness of Modular Mousetrap considering
that in my investigations, though I analyzed only few decks among
all the 17! ~ 3.56 x 10^14 permutations, I obtained again a 51-reformed
deck for s = 1 ; m = 17, as for s = 1 ; m
= 13,
A 39924-CYCLE FROM THE DECK
and, mainly (25th SEPTEMBER 2009)
A 446194-CYCLE FROM THE DECK
1 3 9 19 8 11 7 4 6 18 2 17 10 16 14 15 13 12 5 !!!!!!!!!!!!!!
(clearly, I did not check the correctness of all the reformations, but I have sufficiently tested the FORTRAN program used for these results to believe it!)
File loop_39924_171.pdf (2349 pages!!! ~ 2174 kB!!!) contains the sequence of reformed decks starting from the deck
1 16 11 14 9 8 4 2 5 15 13 6 12 3 10 7 17.
File loop_19_1_446194.pdf (32809 pages!!! ~ 31967 kB!!!) contains the sequence of reformed decks starting from the deck
1 3 9 19 8 11 7 4 6 18 2 17 10 16 14 15 13 12 5.
Consequently, it is highly probable that the above mentioned scores could be improved, if we would study more cases for n prime, for example by means of parallel calculus.
In order to give the most complete answer to question 4), I have inserted, as an example, the data file 17_1_cycles.txt, where I show the number of k-reformed permutations and k-cycles for m = 17 at the end of a run of the FORTRAN program using the "eulerian" technique. They are incomplete results, but they give evidence of the presence of very long reformation sequences and cycles.
Cayley [3] proposed to investigate, at Mousetrap, whatever the number n of cards is, which permutations throw out the cards in the same order of their numbers. He obtained the corresponding permutations for n < 9:
1 ; 1 2 ; 1 3 2 ; 1 4 2 3 ; 1 3 2 5 4 ; 1 4 2 5 6 3 ; 1 5 2 7 4 3 6 ; 1 6 2 4 5 3 7 8 .
Guy and Nowakowski observed that not all the permutations are reformed permutations. On the other hand, the identity permutation 1 2 ... n is always a reformed permutation. Since it is not possible, in general, to arrange the cards so that all the cards may be thrown out in a predetermined order, Cayley [3] posed the following question:
for each n find the winning permutations of 1 2 ... n.
Since our technique starts just from a permutation and tries to rebuild the deck from which the permutation is reformed, the "eulerian" technique can be easily adapted to check if any particular permutation is a reformed deck. In particular, we can very easily give, for every n, the deck producing as reformed permutation the identity 1 2 ... n, giving a positive answer to the original question by Cayley [3] ("investigate, whatever the number n of cards is, which permutations throw out the cards in the same order of their numbers").
Here we report the sequence of the requested decks up to n = 13, but it is a matter of seconds to find the answer for every value of n.
1 [Ca] ; 1 2 [Ca] ; 1 3 2 [Ca] ; 1 4 2 3 [Ca] ; 1 3 2 5 4 [Ca]
; 1 4 2 5 6 3 [Ca] ; 1 5 2 7 4 3 6 [Ca] ; 1 6 2 4 5 3 7 8 [Ca]
; 1 4 2 8 6 3 7 9 5 ; 1 8 2 9 7 3 10 5 6 4 ; 1 10 2 9 6 3 5 8
7 4 11 ; 1 6 2 7 5 3 11 12 8 4 9 10 ; 1 8 2 5 10 3 12 11 9 4 7
6 13 .
We have inserted the symbol [Ca] to indicate
the permutations originally obtained by Cayley in [3].
In the file identity_100.txt it is possible
to read the decks up to n = 100, but it is possible to
build new ones, for whatever value of n, by means of a
FORTRAN program.
ACKNOWLEDGEMENTS
I will highly appreciate any information on improvements of the results reported in this paper and/or of the computer programs to obtain them:
For Mousetrap: the FORTRAN file Guy_ch.for and its text version.
For Modular Mousetrap: the FORTRAN file Guy_MODULAR_CH.for and its text version.
Please, feel free to ask me any question related to the files. My e-mail is bersani at dmmm.uniroma1.it.
REFERENCES
[1] A.M. Bersani, An "eulerian" approach to a class of matching problems, preprint Me.Mo.Mat. n. 14/2005.
[2] A.M. Bersani, Reformed permutations in Mousetrap and its
generalizations, preprint Me.Mo.Mat. n. 15/2005.
[3] A. Cayley, A problem in permutations, Quart. J. Pure Appl.
Math., vol. 1, 1857, p. 79.
[4] A. Cayley, On the game of Mousetrap, Quart. J. Pure Appl.
Math., vol. 15, 1878, pp. 8 - 10.
[5] R.K. Guy, Mousetrap, § E37 in Unsolved Problems in Number
Theory, second edition, Springer-Verlag, New York, 1994, pp. 237
- 238.
[6] R.K. Guy, R. Nowakowski, Mousetrap, Combinatorics, Paul Erdos
is Eighty, vol. 1, D. Miklos, V.T. Sos, T. Szonyi Eds., Janos
Bolyai Mathematical Society, Budapest, 1993, pp. 193 - 206.
[7] R.K. Guy, R. Nowakowski, Unsolved Problems - Mousetrap, Amer.
Math. Monthly, vol. 101, n. 10, 1994, pp. 1007 - 1008.
[8] R. Guy, R. Nowakowski, Monthly Unsolved Problems, 1969 - 1995,
Amer. Math. Monthly, vol. 102, 1995, pp. 921 - 926.
[9] D.J. Mundfrom, A problem in permutations: the game of Mousetrap,
European J. Combin., vol. 15, 1994, pp. 555 - 560.
[10] M.Z. Spivey, Staircase Rook Polynomials and Cayley's Game
of Mousetrap, accepted for publication on European J. Combin.
[11] A. Steen, Some formulae respecting the Game of Mousetrap,
Quart. J. Pure Appl. Math., vol. 15, 1878, pp. 230 - 241.
Related OEIS sequences (The On-Line Encyclopaedia of Integer Sequences - http://www.research.att.com/~njas/sequences/ ): A000166, A002467, A007709, A007711, A007712, A055459, A067950, A127966.