The Day Camp Stacking Game

Question

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.

Answer 1

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.