Suppose you have a deck of n cards, labelled with numbers from 1 to n. You start counting the cards 1,2,3... If the count does not correspond to the number on the card on top of the deck, you move the card at the end of the deck. Otherwise, you put the top card aside and start counting again from 1.
If your count reaches n+1, then you have lost, your deck is a dead-end and the game stops (this would happen by continuing the above example game). Otherwise, if you were able to remove all the cards with this method, then it is a success, and you restart the whole procedure on a new deck of cards, in the order in which you removed the cards.
For example, for n=4, if you start from the deck 1 4 3 2, you start by removing the 1, then you count 1,2,3,4, you remove the 4, then 1,2, and finally 1,2,3 on the last card. This gives you the new deck 1 4 2 3.
Starting again, you remove in order 1 2 3 4. Starting again, you remove the 1, but cannot remove any other card, so the game stops here.
Two cases can occur: either you reach a dead-end at some point, or you fall into a cycle, meaning that you get a previously encountered deck.
THE MODULAR MOUSETRAP
In this variant, you count modulo n. This means that you do not stop at n+1, but continue counting again with 1. Some decks are still dead-ends, like for example 4 3 2 1 (you would be counting infinitely without ever removing any card). Again, you continue playing until you reach either a dead-end or a cycle.
For example, starting from 1 3 4 2, you would remove the 1, then count 1,2,3,4,1,2, remove the 2, and finally remove the 3 and 4. You would get the new deck 1 2 3 4. On this one, you would remove the 1, then count 1,2,3,4,1,2,3,4,1,2, and remove the 2, and finally remove the 3 and 4. You would get again 1 2 3 4, and thus stop because you ran into a cycle (this cycle is trivial, but there may be non-trivial cycles).
WHAT YOU HAVE TO DO
You have to provide 30 initial decks that produce long sequences and that preferably run into a cycle. More precisely, you have to provide decks for both the non-modular and modular versions for values of n from 10 to 25, except for 23 (guess why, designers of programming contests have strange requirements sometimes...).
THE SCORING
The length of a sequence is the number of distinct decks (including the starting one) you encounter before reaching either a dead-end or a previously encountered deck. This means that for cycles, this might be the length of the initial steps, plus the length of the cycle itself. For example, the length of the sequence starting from 1 4 3 2 in the non-modular version is 3, and the length of the sequence starting from 1 3 4 2 in the modular version is 2. More generally, the sequence A B C D E E E E... has length 5 (4+1), and the sequence A B C D E C D E C D E... has length 5 (2+3) (where different letters denote different decks).
For each category, only your "best" entry is considered for the scoring. "Best" means your longest entry with cycle if you have entries with cycles, otherwise your longest entry if all your entries are without cycles. For each category, the reference length is the longest length among the best entries of all participants (the cyclic aspect is not taken into account here). Then, for each category, you get an individual subscore which is the length of your best entry divided by the reference length. Moreover, since cycles are good, you get 1 extra bonus point if your best entry ends on a cycle. As a consequence, a subscore is a number between 0 and 2. Note also that a cyclic sequence is always considered better than a non-cyclic one, even if it is much shorter. So if your best entry is a cycle of length 3, while another participant has a non-cyclic sequence of length 10 as his best entry, you get 1+3/10 = 1.30 points for that category, while he gets only 0+10/10 = 1 point.
Your global score is the sum of the 30 subscores. It is a number between 0 and 60.
HOW TO SUBMIT ENTRIES
First of all, you have to register in order to get your account created.
Then, you can go to the submission page (username and password required), and fill the form with you entry. For convenience of use, your entry will be processed both in the non-modular and in the modular categories (but there is little chance that a same entry gives a good scoring in both categories). After submission, the lengths of the sequences starting from your permutation are computed and eventual cycles are detected.
Important: In the modular category, for values of n of 17 and 19, the entries will not be processed immediately by the web server, but will be processed manually from time to time (I hope every couple of days). This is necessary because those entries might take too much time and I don't want to overload the server. In your My entries page, will you be able to see if your entries have been processed. So, please don't write me e-mails to tell me that your score wasn't updated after you submitted a modular entry for n=17 or 19, and just be patient. On the general Standings page, will you also see the date of the last manual processing.
Very important: In order to avoid overloading the server, you must not use the submission page to compute the length of your sequences. You should only submit what you assume to be your best solutions. I will disqualify any person who submits an "unreasonable" number of entries.
OTHER RULES
Here are a few other rules:
- You cannot have multiple accounts or enter the contest more than once.
- Teams are allowed. However, once you are in a team, you cannot re-enter the contest as an individual, and conversely once you are registered as an individual, you are not allowed to join a new team. Moreover, the composition of teams cannot be changed after their creation. Please indicate the names of all participants when registering.
- People from Aarhus University are not allowed to join the contest.
- How ties are resolved: when two entrants get exactly the same score, the tie is resolved by looking at the time of their last entry (the older one gets first). If there is still a tie, the first will be the one with the lower number of entries.
- I am in no way responsible of collateral damages induced by this contest. This includes, but is not limited to: soulmate quitting the house because you spent your nights on the contest, boss getting angry because you are using all the CPUs of all your co-workers, etc...
DISCUSSION GROUP
If you want to discuss about this contest, please join the Mousetrap Programming Contest mailing list. Any kind of discussion is allowed, provided it has a direct link with this contest. You are free to post your results, entries or code (but of course you might not want to reveal your secrets until the end of the contest).
If you have questions about this contest or a technical problem, please post a message to this list instead of sending an e-mail directly to me, as some other participants might help you faster than I can.
Official announcements about this contest will also be made on this list (and also on Al Zimmermann's discussion group).
REFERENCE
The game of mousetrap was invented by Cayley (there is a reference to it in MathWorld). For those of you who have access to it, this problem is inspired by the section E37 of Richard Guy's book "Unsolved problems in number theory".
Back to the main page.