Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

(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
share|improve this question
    
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

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.