7
$\begingroup$

My friend works at a day camp as a counselor and he told me about an interesting game he plays with his group of kids.

You have a perfectly shuffled, regular $52$-card deck and a group of $2 \leq n < 52$ kids under your supervision. You ask the kids to sit in circle and randomly distribute a card to each one of them. Thus, each individual gets either a red or a black card (depending on the suit) that they stick on their forehead for everyone to see. The counselor then sits in the middle of the circle and passes through the remaining $52-n$ cards from top to bottom of the deck and show each card to the group. The rules are as follows:

  1. Each kid has an assigned chair to start the game. This chair can either be vacant or occupied during the game and cannot be moved.
  2. If a red (resp. black) card is shown, each kid with a red (resp. black) card sits on the chair to his/her left. If someone is already on the chair, the kid sits on him/her.
  3. If a kid has someone on top of him/her, he/she cannot move when his/her color is drawn, i.e. only kids on top of a stack can move.

If two kids have the same color and this color is drawn, they rotate (shift) clockwise by $1$, $e.g.$ if $n=4$ and the colors are $RRBR$ and red is drawn, then the new configuration is $R \sharp (BR) R$, where $(BR)$ means black kid under red kid and $\sharp$ denotes an empty seat. It is possible that no kid moves on a card. The game ends when there are no more cards in the deck. Everybody wins in this game, like any day camp game.

I found this game extremely fascinating due to its underlying mathematical structure. It gives rise to some deep mathematical problems which I am currently trying to understand.

Let's assume the game does not stop when the deck of cards is empty, but instead after some multiple (called turn) of the remaining cards are shown, i.e. after $(52-n)m$ cards are shown for some $m$. I wish to analyse two cases, namely cycling though the deck after each turn or shuffling the deck after each turn. By cycling, I mean that the first card that was shown in the first turn is the first card shown in the second turn and so on.

  1. In case of cycling, what is the probability that, at some point in the game, all $n$ children are stacked on top of each other?
  2. What about shuffling?
  3. In both cases, what happens when we let $m \to \infty$?

I know very little about probabilities, let alone combinatorics, but I feel like these questions might be difficult to answer. This problem might even be undecidable. The game somewhat reminds me of an "ordered" version of the Tower of Hanoi with additional rules, which I know how to solve but I can't see how it could be useful in the current situation. One thing I noticed is that in either cases, the full stack $-$ if it ever happens $-$ will alternate in color as a direct corollary of rule 2.

I had some ideas, for instance considering a graph with charges on each vertex and then realizing a stacking as an edge contraction and charge transfer, but this seems overly complicated.

How would you go about this problem? Any help would be greatly appreciated.

$\endgroup$
  • 1
    $\begingroup$ My first instinct would be to write a computer simulation. $\endgroup$ – Bridgeburners Aug 18 '14 at 20:30
  • 1
    $\begingroup$ You need to be clearer about the rules. It is not clear that somebody moves every turn. Let there be four kids, with 1 and 3 having black cards and 2 and 4 having red. If the first card is red, you will have two stacks of two kids each, with the top one having a red card, and two empty spaces. If you draw a black card next, nobody can move. If you draw a red card next, what happens? Both the top kids seem to want to sit on the other. If you have four kids in a row with red cards and draw red, what happens? $\endgroup$ – Ross Millikan Aug 18 '14 at 21:11
  • $\begingroup$ Good catch. I edited my question. I added chairs so that it's clearer that the circle cannot be shrank. I also took care of the case where two kids with the same color are next to each other. Hopes this is clear now. $\endgroup$ – Hubble Aug 18 '14 at 21:32
  • $\begingroup$ Is rule 4 a repetition of rule 2 or is it trying to say something additional? (I assume that "clockwise" and "left" mean the same thing here). $\endgroup$ – Peter Taylor Aug 19 '14 at 12:50
  • $\begingroup$ @PeterTaylor: it is, but Ross wanted some specifications. I removed it from the rule, but not from the question. $\endgroup$ – Hubble Aug 19 '14 at 17:20
2
$\begingroup$

I am one of the friends mentioned in the question!

Here are my ideas yet. I will edit this post as I get deeper in the resolution, or if I find any other ideas. I will only be able to work on this on the side during free time.

One approach, which would reduce the first part of the problem to a finite computational task, would be to find the number of outcomes that yield a colouring of the circle of kids through the orbit-stabilizer formula for the dihedral group equipped with at most 2 colours of vertex, i.e. just as we would solve the necklace problem with 2 colours colouring for $k=2$ up to $k=n$ vertex.

Each of those configurations (outcomes) is associated to an easily computed probability. Then, the probability of drawing a black or a red card is also easily computed with respect to a given outcome.

We would now be left with formalizing the state of the stacks. I have no clear idea on how we can go about doing that yet.

Observe though that since the only way a stack can occur is by a sequence $BRBRBRB...$ or $RBRBRBRB...$, it is readily seen that no configuration in which $|b-r|>2$, where $b=$#$B$ and $r=$#$R$ can obtain a stack composed of all the kids... If we could characterize the cases $b=r$ and $|b-r|=1$ in a similar way, the case where $m\rightarrow \infty$ with shuffles would be solved.

$\endgroup$
  • $\begingroup$ I'm not sure how easy it is to determine if a configuration is "stackable" given $n$ and $m$. $\endgroup$ – Hubble Aug 20 '14 at 17:11
  • 1
    $\begingroup$ I have edited my post to underline that this is exactly what is left to solve with this approach, but I suspect that any other approach would need to deal with that problem anyway. $\endgroup$ – EkS Aug 20 '14 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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