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:
- 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.
- 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.
- 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.
- 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?
- What about shuffling?
- 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.