# 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

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.