*
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: 19

MAX 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

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.**