Posers and Puzzles
27 Mar 07
27 Mar 07
2 edits
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.
28 Mar 07
Originally posted by GregMThat'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?
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.
28 Mar 07
Originally posted by DeepThoughtWe can say some things about a stable state without constructing one:
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?
-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.
29 Mar 07
Originally posted by Nicky4815I 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).
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.
29 Mar 07
Originally posted by Nicky4815Would you expect that to be true for any value of n?
The one way to arrive at that configuration is from the same configuration.
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
29 Mar 07
Originally posted by Nicky4815I'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:
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.
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.