Cards problem

Take a pack of 52 cards with 3 jokers, so there are 55 cards. Put them in piles with any number of cards in each pile. Take 1 card from each pile and make a new one. Keep repeating this - what do you end up with? Can you show that this always happens from any initial configuration (describing an algorithm that could be implemented on a computer is sufficient)?

To illustrate what is happening - say you start with 4 piles, a pile of 44, one with only 1 card in and the other two piles both with 5 cards:

44, 5, 5, 1 ---> 43, 4, 4, 0, 4 = 43, 4, 4, 4 ---> 42, 3, 3, 3, 4 ---> 41, 2, 2, 2, 3, 5 etc.

I orginally heard this one on the BBC Radio 4 program Puzzle Panel.

I haven't tested this at all, but...

You ought to end up with piles of 1,2,3,4,5,6,7,8,9,10, I think, because that pattern is stable.

The 1,2,3,...,n pattern would only be possible with decks of size of the form n*(n+1)/2.

Originally posted by GregM
I haven't tested this at all, but...

You ought to end up with piles of 1,2,3,4,5,6,7,8,9,10, I think, because that pattern is stable.

The 1,2,3,...,n pattern would only be possible with decks of size of the form n*(n+1)/2.

That's the first part (well done for spotting the n(n+1)/2 ingredient), but how do you show that you always get that from any starting configuration? Also suppose you have just the basic set of 52 cards - are stable states possible?

Originally posted by DeepThought
That's the first part (well done for spotting the n(n+1)/2 ingredient), but how do you show that you always get that from any starting configuration? Also suppose you have just the basic set of 52 cards - are stable states possible?

We can say some things about a stable state without constructing one:

-the largest pile is equal to the number of piles
-there is exactly one pile of one card (which runs out and is replaced by the new pile)

Now, the pile of one card requires a pile of two cards to decay into it, and the pile of two requires a pile of three, and so on. It seems that the only stable configurations are of the 1,2,...,n form.

Every configuration must eventually fall into a repeating loop, because there are only a finite number of possible configurations.

I'm not sure how to show that a 55 card deck will go to 1,2,...,10; I'll have to think about it.

I would say that you could not reach the stable state. The one way to arrive at that configuration is from the same configuration. So a stable state would only be reached if it began in the stable state.

Originally posted by Nicky4815
I would say that you could not reach the stable state. The one way to arrive at that configuration is from the same configuration. So a stable state would only be reached if it began in the stable state.

I checked this on a computer - you always get to a stable state in less than 100 cycles. Try it with 6 coins (stable is 3 + 2 + 1, eg 6 --> 5 + 1 --> 4 + 2 --> 3 + 2 + 1). I doubt there is a way of proving it analytically, but it's a straightforward matter to start off in any given state and cycle through the procedure. The tricky(ish) bit is to find an algorithm that reliably generates all possible starting states (55, 54 + 1, 53 + 2, 53 + 1 + 1, etc).

Originally posted by Nicky4815
The one way to arrive at that configuration is from the same configuration.

Would you expect that to be true for any value of n?

for n=3 you don't need to start with 1,2,3
e.g.
4,2
3,1,2
2,0,1,3 => 2,1,3
1,0,2,3 => 1,2,3
1,2,3
1,2,3

or
2,2,2
1,1,1,3
2,4
1,3,2
2,1,3
1,2,3

As an example,

11, 9, 8, 7, 6, 5, 4, 3, 2 goes to
10, 8, 7, 6, 5, 4, 3, 2, 1, 9 = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Originally posted by Nicky4815
I would say that you could not reach the stable state. The one way to arrive at that configuration is from the same configuration. So a stable state would only be reached if it began in the stable state.

I'm not sure if this is true or not, but not all initial states will end up stable. Suppose n=2 and we start with one pile of 2:

2
1,1
0,0,2 -> 2
1,1
0,0,2 -> 2
1,1
etc...

This one will oscillate forever between 1,1 and 2.