Posers and Puzzles

Posers and Puzzles

  1. Standard memberDeepThought
    Losing the Thread
    Cosmopolis
    Joined
    27 Oct '04
    Moves
    80309
    27 Mar '07 15:192 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.
  2. Joined
    13 Dec '06
    Moves
    792
    28 Mar '07 02:24
    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.
  3. Standard memberDeepThought
    Losing the Thread
    Cosmopolis
    Joined
    27 Oct '04
    Moves
    80309
    28 Mar '07 03:06
    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?
  4. Joined
    13 Dec '06
    Moves
    792
    28 Mar '07 03:22
    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.
  5. Joined
    19 Feb '07
    Moves
    2617
    29 Mar '07 12:49
    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.
  6. Standard memberDeepThought
    Losing the Thread
    Cosmopolis
    Joined
    27 Oct '04
    Moves
    80309
    29 Mar '07 13:24
    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).
  7. Joined
    28 Nov '05
    Moves
    24334
    29 Mar '07 13:27
    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
  8. Joined
    13 Dec '06
    Moves
    792
    29 Mar '07 19:28
    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
  9. Standard memberPBE6
    Bananarama
    False berry
    Joined
    14 Feb '04
    Moves
    28719
    29 Mar '07 19:50
    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.
Back to Top