Chaos tag is way slower than team tag

Posted June 18, 2017

FiveThirtyEight's Riddler this week about a chaotic game of tag traces back to Austin Shapiro. Here's the puzzle:

On a sunny summer day, you’ve gone to the park with your friends. After the picnic is eaten, you decide to enjoy the weather by playing a nice game of chaos tag. For those uninitiated in the joys of chaos tag, you explain the following rules:

1. Any group of two or more people can play. All players are active at the start of the game.
2. Active players can run around and tag other active players.
3. A player who is tagged becomes inactive and must sit on the spot where they were tagged.
4. An inactive player becomes active again when the player who tagged them is tagged.
5. Victory is achieved by being the only remaining active player.

Suppose N of you are at the park that day. If all active players are equally likely to tag someone and any of the possible targets are equally likely to be tagged, how long will the game last on average, as measured in tags? (For example, with two players, the game always ends in one tag; with three players, the expected length of the game is three tags.)

Extra credit: It’s been a while, so let’s offer up a 🏆 Coolest Riddler Extension Award 🏆. Tweak the rules, introduce some park geometry, make some players faster, or suggest your even more creative twist on this puzzle. The winner gets a shiny emoji trophy next week.

I did a bunch of calculation to work out the answers for \(N\) going up to 5. I eventually found a pattern, and the trick was to have the players keep track of score. Answer: \(2^{N-1} - 1\).

Solution

We're going to add a scoring system to chaos tag. Each player starts with 0 points. Every time you tag someone else, your score doubles, plus one. So, if you've tagged one person, your score is 1. If you've tagged two people, your score is 3. If you've tagged \(k\) people, your score is \(2^k - 1\). However, if you get tagged, your score resets to 0.

We're using this scoring system because it has the following property:

Observation 1: When a random tag happens (that is, when a random active player tags another random active player), the expected increase in the sum total of players' scores is 1.

Proof of Observation 1: Consider any player. If they get tagged, they lose all their points. If they tag someone else, they gain that same number of points, plus one. So, the expected points gained by a random player making a tag is one more than the expected points lost by a random player getting tagged. Since a unifomly random player makes a tag and a uniformly random player gets tagged, the expected net change in total score is 1. \(\square\)

Observation 1 implies the following.

Observation 2: The expected total score after \(t\) random tags is \(t\). (In other words, the total score minus the number of tags that have happened forms a martingale.)

We'll finish solving the problem by considering the total score at the end of the game.

Observation 3: At the end of the game, the total score is \(2^{N-1} - 1\).

Proof of Observation 3: The only way for you to win the game is to tag all \(N - 1\) other players yourself (anyone who was tagged by someone else will become active again when you tag their tagger). At that point, you'll have \(2^{N - 1} - 1\) points, everyone else will have 0 points. \(\square\)

By Observation 2 (and the optional stopping theorem), the expected number of tags in the game is equal to the (expected) score at the end of the game. So, by Observation 3, the expected number of tags is \(2^{N - 1} - 1\).

Comparison: Chaos tag vs. team tag

The two tag games are somewhat similar - lots of people are eligible to tag and be tagged, and once you are tagged, your fate is linked to that of the person who tagged you. We already saw that chaos tag lasts \(2^{N - 1} - 1\) tags in expectation, so maybe team tag should have about the same length?

Actually, team tag was the subject of a previous Riddler, but in disguise. In this Riddler about a colorful box of balls, each ball represents a player, each color represents a team, and the process of drawing a pair of balls represents one player tagging another. Here's my write-up for that puzzle. From that, we know that the expected length of team tag is \((N - 1)^2\) tags, quadratic in \(N\). Meanwhile, chaos tag requires an expected number of tags that is exponentially in \(N\), which is way, way longer than team tag.

I suppose this is reasonable. In chaos tag, if one of your team members gets tagged, it only sets your team back a little bit. But in chaos tag, if you get tagged, everyone that you've tagged goes free and you have to start over.

Extension: Break-free chaos tag

As an extension, here's a variant on chaos tag.

Break-free chaos tag is played like chaos tag, but with one difference: Each time you are inactive, you have one chance to flip a fair coin. If it comes up heads, you "break-free" and become active again. You win the game when you are the only active player, and all other players have used up their coin flips.

If there are \(N\) players, how long does break-free chaos tag last on average?

Note that when the person who tagged you gets tagged, you become active again regardless of that person's coin flip.

Solution: We modify the scoring system above. Everyone starts with 0 points. Whenever you tag someone and that person's coin flip comes up tails, your score triples, plus two. So, if you've tagged \(k\) people who proceed to flip tails, then you have \(3^k - 1\) points. Whenever you get tagged, you go back to 0 points (regardless of your coin flip).

In this system, if you get tagged you lose all your points, while if you tag someone you have a \(\frac{1}{2}\) probability of gaining twice that number of points, plus two. That is, the expected point gain of tagging someone is one more than the loss from getting tagged. So, Observations 1 and 2 from above still hold in this game.

The expected number of tags in the game is again equal to the total score at the end of the game, which in this case is \(3^{N - 1} - 1\).