# Self-collisions in a stack of cards

(Copied verbatim from: A Project Euler thread I made in December of 2009.)

Lets say you have cards numbered from 1 to 5. You want to organize them into a stack such that you can move 1 card from the top to the bottom and turn over the next card to reveal a 1. Put it off to the side and move two cards from the top of the stack (one at a time) to the bottom. The next card is revealed and is a 2, which is then set aside. Repeat until you have 1 card left which will be 5. In order to achieve this, the cards must be ordered as such: [3, 1, 4, 5, 2] But what if I want to order 10 cards this way? Well...the required pre-order is then [9, 1, 8, 5, 2, 4, 7, 6, 3, 10]. Then I started wondering if there were any cases where the card's number was its actual position in the stack before the dealing. What a surprise! 7 ([5, 1, 3, 4, 2, 6, 7]) has 4! It turns out that 7 is the first number where the sequence generated thus has more than 2 self-collisions, as I call them. The first one to have 5 is 543, the first one to have 6 is 3117, and the first one to have 7 is 3226. I have not found one for 8 yet, but there may be a 9 before the first 8. If anyone can find an analytical solution to the following questions...I will be greatly amazed... :P

What is the first one to have 8 self-collisions? What about 9? What about 10?

P.S. The sequence for 5 can be generated thus (easily generalized):

xxxxx
x1xxx
x1xx2
31xx2
314x2
31452

-
I do not think that it is likely that this question has a good answer. I think that a question of the type "Will the highest number be the last to be eliminated?" in analogy to the Josephus problem is easier and I have no idea how to address it (although this is no conclusive argument, of course, as the more complicated question could have a simpler answer in principle). – Phira May 9 '11 at 8:12

The first number to have 8 collisions is 57,063. There are no cases of 9 or more collisions below 1,000,000 cards.

In general, based on some rough approximations (basically, assuming the number of collisions per deck to be Poisson distributed with mean 1), I'd expect the first number with $n$ collisions to have magnitude more or less comparable to $n!$. So I'd guess that the first number with 9 collisions probably lies somewhere in the six-digit range, although of course it might appear sooner or later than that by coincidence. (Edit: It seems that it is indeed later.)

Ps. If anyone else wants to try solving problems like this by brute force, I recommend storing the deck in a binary tree. This allows both removing a card and skipping $k$ cards to be done in $O(\log n)$ operations, where $n$ is the size of the deck, giving a total running time of $O(n \log n)$. I doubt it's possible to do much better than that.

-