Rock-paper-scissors-hop: Discrete hops are hard, so follow the continuous firefly

Posted August 26, 2018

This week, FiveThirtyEight's Riddler has a puzzle about a gym class game called rock-paper-scissor-hop, which came from Taylor Firman. Here's the puzzle:

The following delightful video has been making the viral rounds:

Let’s call this game rock-paper-scissors-hop. Here is an idealized list of its rules:

• Kids stand at either end of N hoops.
• At the start of the game, one kid from each end starts hopping at a speed of one hoop per second until they run into each other, either in adjacent hoops or in the same hoop.
• At that point, they play rock-paper-scissors at a rate of one game per second until one of the kids wins.
• The loser goes back to their end of the hoops, a new kid immediately steps up at that end, and the winner and the new player hop until they run into each other.
• This process continues until someone reaches the opposing end. That player’s team wins!

You’ve just been hired as the gym teacher at Riddler Elementary. You’re having a bad day, and you want to make sure the kids stay occupied for the entire class. If you put down eight hoops, how long on average will the game last? How many hoops should you put down if you want the game to last for the entire 30-minute period, on average?

To get you started, here’s how a single game might unfold:

To clarify a couple rules based on the animation:

• When a new player comes in, they start not in the first hoop, but right behind it; the new player hops into the first hoop as the player who just won rock paper scissors takes their next hop.
• The last game of rock-paper-scissors that the winner plays is standing in the last hoop, while their opponent stands in the same hoop. Then, the winner takes one more hop to win the game.
• We will make the gross simplification that rock-paper-scissors is completely a game of chance, independent for each round, rather than a game of skill, intellect, dexterity, and strength. In each round independently, we assume that a player wins, loses, or ties each with equal probability.

I really like this kind of puzzle. My first time through solving it, I had to go through a (somewhat nice but) ultimately overcomplicated process to arrive at a remarkably simple pattern. But, if the answer is a simple pattern, there should be some way to solve the problem where the pattern comes out naturally! So, I tried a totally different approach to try to get the pattern to come out, and I ended up with what is below.

There is one thing that is a little annoying about this problem: When a kid wins, he hops half way to the end to have a match-up with his next opponent, but it's not always exactly half way. Whether it is equal to or less than half way depends on whether the kid is standing in an even- or odd-numbered hoop. And it is also annoying that some of the match-ups take place with both kids in the same hoop, and some one-apart. There seems to be a lot of casework built into the problem; it would be nice to find a solution that avoids casework!

Rounding (and the prospect of casework) becomes an issue because the kids can only stand in discrete hoops - that is, there is some amount of space between every two points where a kid can stand. Everything would be a lot cleaner if the kids could stand at a continuously varying set of points; if the kids were allowed to stand at any point along an interval, the problem could have been written so that the kids meet each other exactly half way.

Our strategy is to transform our discrete puzzle into a related continuous puzzle. But, we still want to get an answer to the original puzzle. So, the trick is going to be to modify the puzzle such that it's equivalent to the original puzzle (has the same answer), but in a way allows us to think about it continuously. We will soon introduce a firefly that will be flying around the gym (and may find itself at any real point in an interval).

Splitting the problem into number of match-ups and number of hops

Before we get into the crazy reinterpretation of the rules, we're going to use some basic tricks to break down the problem. If we want to calculate the total amount of time in a game, we can calculate it as

\[ \text{total time in seconds} = (\text{seconds hopping}) + (\text{seconds playing rock-paper-scissors}). \]

We want the expected total time, so taking the expected value of both sides,

\[ \DeclareMathOperator*{\EE}{\mathbb{E}} \EE[\text{total time in seconds}] = \EE[\text{seconds hopping}] + \EE[\text{seconds playing rock-paper-scissors}]. \]

We're allowed to split the right-hand side into the sum of two expected values because of the amazing fact expected value is linear even for random variables that are dependent. So, we can separately consider the number of seconds spent hopping and the number of seconds spent playing RPS.

Since each hop takes one second, the number of seconds hopping equals the number of hops.

We can break down the time playing rock-paper-scissors as

\[ \text{seconds playing RPS} = (\text{# of match-ups of RPS}) \cdot (\text{average # seconds per match-up}). \]

A match-up will refer to playing as many rounds of rock-paper-scissors as necessary until there is a winner. Some rounds may result in a tie, so some match-ups may require more than one round (hence, more than one second).

Taking the expected value of both sides of this,

\[ \EE[\text{seconds playing RPS}] = \EE[\text{# of match-ups of RPS}] \cdot \EE[\text{average # seconds per match-up}]. \]

We're allowed to split the right-hand side into the product of two expected values because the two random variables are independent of each other (to split up products we need independence, even though we don't need this for sums). In particular, the expected number of seconds in a match-up is the same for all match-ups, regardless of how many match-ups have happened before, or how many are going to happen after.

Let's now calculate the expected number of seconds per match-up. We'll use the following lemma, which we'll also use a few more times later in the solution.

Lemma. Let \(0 \lt p \lt 1\). Suppose we have a game consisting of (potentially) multiple rounds, and in each round, the game has probability \(p\) of ending. Then the expected number of round is \(\frac{1}{p}\).

Proof. The game lasts at least \(1\) round with probability \(1\), at least two rounds with probability \(1 - p\), three rounds with probability \((1 - p)^2\), and so on. So, the expected total number of rounds is \[1 + (1 - p) + (1 - p)^2 + (1 - p)^3 + \cdots,\] which is a geometric series converging to \(\frac{1}{p}\). \(\square\)

This proof is perhaps a little bit opaque, so here's another way to think about it: Consider playing many games in a row, back-to-back. When one game starts, just start a new one. After many, many plays through the game, if \(r\) rounds happened, about \(pr\) of those rounds results in the game ending, so there were about \(pr\) total games, so the average number of rounds per game is about \(\frac{r}{pr} = \frac{1}{p}\). Let's apply this to the current situation: In each round of rock-paper-scissors, the match-up has a \(\frac{2}{3}\) probability of ending, so the expected number of rounds per match-up is \(\frac{3}{2}\). Plugging this back into our equations, we get a nice formula for the number of seconds per game.

Proposition. The expected number of seconds per game of rock-paper-scissors-hops is \[ \EE[\text{total time in seconds}] = \EE[\text{# of hops}] + \frac{3}{2} \EE[\text{# of match-ups of rock-paper-scissors}]. \] So, our goal from this point forward will be to calculate the expected number of hops, and expected number of match-ups of RPS. Before doing that, we'll introduce our modification to the puzzle, the firefly in the room.

The firefly that flies exactly half way: turning a discrete problem into a continuous one.

We are going to lay the whole hoop setup down on a number line to help us with some upcoming calculations. Before we do that, though, we are going to divide the the interval \([0, 2N + 1]\) into \(2N + 1\) zones of length \(1\). There are three kinds of zones:

• The first and last zones, \([0, 1]\) and \([2N, 2N + 1]\), we will call endzones.
• The zones whose left endpoint is odd, \([1, 2], [3, 4], [5, 6], \dots, [2N - 1, 2N]\), we will call O-zones. There are \(N\) of these.
• The remaining zones, \([2, 3], [4, 5], [5, 6], \dots, [2N - 2, 2N -1]\), we will call X-zones.

(In the diagrams, we'll take \(N = 4\) for most of our examples.)

We will take our hoops to have radius one, and we will place them so that each hoop has its center at the center of an O-zone, that is, at \(1.5, 3.5, 5.5, \dots, 2N - 0.5\) (The "O" is for the shape of a hoop). This also means that at the center of each X-zone, two hoops meet (making an "X" shape). The left end of the left-most hoop and the right end of the right-most hoop are in the center of the endzones.

A firefly has gotten into the room, and it would like to fly around to catch all the action. It wants to get the best possible view of all events. We'll use the term event to refer to

• a match-up, that is a run-in between two kids (which causes them to play RPS), or
• a win, that is, a kid making it to the final hoop, thus winning the game.

If two kids run into each other in the same hoop for a match-up, the firefly would like to be in that hoop as well, specifically in the corresponding O-zone (anywhere in the zone).

If two kids run into each other in adjacent hoops for a match-up, the firefly would like to be in the X-zone between them.

And, if a kid wins the game, the firefly would like to be right there beside them, in that endzone.

To try to always be in the correct zone, the firefly will follow this strategy: Assume the firefly is the correct zone for some match-up event. Then, for the next event:

• If the player on the right (who is moving to the left) wins the match-up, the firefly flies half of the way to \(0\).
• If, instead, the player on the left (who is moving to the right) wins the match-up, the firefly flies half of the way to \(2N + 1\).

For example, if the players run into each other both in the third hoop, then the firefly might be at, say, \(5.6\). If the right player wins, it flies to \(2.8\), which is in the correct zone for the next run-in, which will feature one kid in the first hoop and one in the second.

Proposition. If the firefly is in the correct zone for any event, and then follows the above strategy, it will be in the correct zone for all following events for the rest of the game.

You can verify this Proposition by considering an arbitrary position for the firefly in an arbitrary O-zone, and then an arbitrary position in an arbitrary X-zone. One of the goals of this solution was to avoid the need to split into cases, and the only casework in the proof is hidden in this Proposition, plus one other that will come up when we start counting hops. And perhaps the casework it is a little more palatable because the Propositions are both geometric, and if you think about it the right way, you don't even really need to divide into cases.

After every event - as long as that event isn't a win - the firefly flies to the correct zone for the next event. If there is a win, there is no next event. Soon, we'll modify the rules slightly so that the idea of the "next event" makes sense even when the firefly is in an endzone and the game is over.

Playing many games in a row

We are going to modify the rules to make the kids play many games in a row. This will help us calculate expected number of match-ups per game. Specifically, as the number of games played goes to infinity, the number of match-ups per game will converge to the expected number by the Law of Large Numbers.

Rule change. When a kid gets to the last hoop and wins the game, that game is declared over, and a champion is crowned, but that champion doesn't stop playing. Instead, the champion stays in place and plays a bonus match-up of RPS against the first kid in line. If the champion wins that match-up, they play another bonus match-up against the following person in line. This continues until the champion loses a match-up. At that point, the champion steps out and a new game of rock-paper-scissors-hop begins, with the first kid in each line.

With this rule change, there are now three kinds of events that the firefly wants to be the right place for:

• A (standard) match-up, which takes place during the course of a game.
• A win, where a kid makes it to the final hoop, the game ends, and the new champion plays a bonus-match up that does not count as part of any game.
• A victory lap, where a champion who has already won one or more bonus match-ups plays an another bonus match-up.

When a champion is on a victory lap, the firefly would like to stay in the same endzone. Then, after the champion loses a bonus match-up and a new game begins, the firefly would like to fly to the right position for the first match-up of the new game.

Conveniently for us, the firefly doesn't have to change its strategy to accomplish this. It can continue to use its fly-half-way strategy.

Proposition. Even with the rule change, if the firefly is in the correct zone for any event, and then follows the above strategy, it will be in the correct zone for all following events, including in future games.

For example, suppose the player from the right makes it to the left-most hoop, and becomes the champion. If they win their first bonus match-up, the firefly flies halfway to \(0\), which means staying in the endzone.

If the champion loses their first bonus match-up instead, the firefly flies to a point in the middle zone, \([N, N + 1]\), which is the right place to be for the first match-up of the next game.

We should note that the above rule change eliminates the final winning hop at the end of each game. So, when we find the expected number of hops per game under the modified rules, we'll need to add one to get the answer under the original rules.

We will make one more change to the rules.

Rule Change. The kids will play many games, but for the first game (and only the first game), instead of starting at either end of the row of hoops and meeting in the middle, they will start somewhere else. Specifically, the firefly starts at a uniform random point in the interval \([0, 2N + 1]\), and the kids arrange themselves so that the firefly is in the correct location for the first event (for example, if the firefly is in an O-zone, the kids have their first match-up in that hoop).

Since this changes the rules of the first game, if we tried to calculate the expected number of match-ups in that game, we would not necessarily get the correct answer under the original rules. But, all subsequent games are played normally, so as the number of games goes to infinity, the first game won't matter, and the average number of match-ups per game will converge to the correct expected value.

We made this last rule change because it gives us a mathematical advantage: During every event, the firefly is at a uniform random point in the interval \([0, 2N + 1]\). This is true for the first event, because we changed the rules to make it true. After the first event, the firefly has a \(1/2\) probability of flying left, landing at (because the firefly had been at a uniform random point) a uniform random point in the interval \([0, N + 1/2]\), and a \(1/2\) probability of flying right, landing at a uniform random point in \([N + 1/2, N + 1]\). That means that for the second event, the firefly is at a uniform random point in \([0, N + 1]\).

The location of the first and second events are certainly not independent of each other, but this won't matter when we take expected value. Similarly (by induction), for each subsequent event, the firefly is at a uniform random poin in \([0, N + 1]\).

We are now mostly done transforming our discrete problem about kids into a continuous problem about a firefly, and we are ready to start calculating some expected values.

Expected number of match-ups per game

We have done a lot of work to get to this point, and now we get to see the benefits in calculating the expected number of match-ups per game. The kids play many games, and in the course of this, many events happen. Each event can consist of either a (standard) match-up, a win, or a victory lap.

A standard match-up happens when the firefly is in one of the \(2N - 1\) zones that is not an endzone. Since the firefly is in each zone with equal probability, on average a \(\frac{2N - 1}{2N + 1}\) fraction of events will be a match-up.

The other \(\frac{2}{2N + 1}\) fraction of events (in expected value) happen with the firefly in an endzone, and so are either a win or a victory lap.

How many bonus match-ups does a champion play, on average? They automatically get at least one bonus match-up, and they have a \(1/2\) probability of winning each bonus match-up and playing another (and a \(1/2\) probability of losing). So, by our Lemma from above, their expected number of bonus match-ups is the reciprocal of \(1/2\), which is \(2\). That means at the end of each game, there is exactly \(1\) win event, and expected value of \(1\) victory lap.

We know that wins and victory laps account for an expected \(\frac{2}{2N + 1}\) fraction of events, so an expected \(\frac{1}{2 N + 1}\) fraction of events are wins, and \(\frac{1}{2 N + 1}\) are victory laps.

So in expected value, the number of (standard) match-ups per win event is \(2N - 1\). But the number of wins per game is always exactly one. So, we can conclude that the expected number of match-ups per game is \(2N - 1\).

Expected number of hops per game

We want to count the number of hops per game, but part of the the goal of this solution is to talk about the firefly, who moves continuously, instead of the kids, who move in discrete steps. So before we can start counting hops, we need to figure out how the firefly's movement translates into a number of hops.

Let's take two consecutive events, and count the hops that happend between them. There are always two kids hopping at once, but let's just focus on the one who has been in the game for longer, the one who just won a rock-paper-scissors match-up. That kid has a movement pattern that is very similar to that for the firefly.

That kid and the firefly have similar movement, although the two might travel slightly different distances. So how do they compare?

Proposition. Take any event, and look at the kid who won at rock-paper-scissors. The number of hops that kid makes before the next event is equal to the number of O-zones that the firefly crosses into between those same two events. Those hoops that the kid hops into correspond exactly with the O-zones that the firefly flies into.

You can check that this proposition holds no matter what zones the firefly starts and ends in, and which direction it is moving. With this proposition, we can stop reasoning about the kids and the hoops, and instead think about the firefly.

We would now like to count how many times the firefly enters an O-zone. But actually, every-other time the firefly crosses an integer, it is entering an O-zone (even though it sometimes changes direction). This is because whenever it leaves an O-zone, it enters either an X-zone or endzone, and every time it leaves an X-zone or endzone, it enters an O-zone. So, to calculate the expected number of hops, instead of calculating the expected number of times the firefly enters an O-zone, we can instead calculate half the expected number of times the firefly crosses an integer.

\[ \EE[\text{# of hops per game}] = \frac{1}{2} \EE[\text{# of times the firefly crosses an integer per game}]. \]

To calculate the number of integers crossed per game, we'll calculate the expected number of integers crossed between two events, and then we'll multiply that by the expected number of events per game. By "events per game," we'll include all events between the start of one game and the start of the next (including any bonus match-ups). Here we are again using that expected value is multiplicative for independent random variables.

\[ \EE[\text{# of hops per game}] = \frac{1}{2} \EE[\text{# of events per game}] \cdot \EE[\text{# of integer crossings between two events}]. \]

Since one in \(2N + 1\) events is a game-winning event, there is an expected value of \(2N + 1\) events per game. One might be concerned that this includes hops that are made in the period between games, but that is okay, because the firefly does not cross any integers during that period. It's actually important that we count those periods, so that we can continue to assume that the firefly is at a uniform random position in \([0, 2 N + 1]\) for each event.

Let's now count the expected number of integer crossings between two consecutive events. For \(k\) an integer, let's calculate the probability \(p_k\) that the firefly crosses the integer \(k\) between two events. Then (by linearity of expectation) the expected total number of integer crossings will be \(p_1 + p_2 + p_3 + \dots + p_{2 N}\).

\[ \EE[\text{# of hops per game}] = \frac{1}{2} (2 N + 1) (p_1 + p_2 + p_3 + \dots + p_{2 N}). \]

Consider \(1 \leq k \leq N\). The firefly will cross \(k\) if it starts between \(0\) and \(k\) and flies to the right, or if it starts between \(k\) and \(2k\) and flies to the left. Altogether, this happens with probability \(p_k = \frac{k}{2N + 1}\).

For \(N + 1 \leq k \leq 2N\), we have the mirror-image: the probability that the firefly crosses \(k\) is \(p_k = \frac{2N + 1 - k}{2N + 1} = p_{2 N + 1 - k}\).

So, the expected number of hops per game is

\[ \begin{align*} \EE[\text{# of hops per game}] &= \frac{1}{2} (2 N + 1) (p_1 + p_2 + p_3 + \dots + p_{2 N}) \\ &= \frac{1}{2} (2 N + 1) ( 2 ( p_1 + p_2 + \dots + p_N) ) \\ &= (2 N + 1) p_1 + (2 N + 1) p_2 + \dots + (2 N + 1) p_n \\ &= 1 + 2 + 3 + \dots + N \\ &= \frac{N (N + 1)}{2}, \end{align*} \]

which is the \(N\)-th triangular number.

This calculation was done with our modified rules, without the "winning hop" off the end when the game finishes. Counting the winning hop, the total number of hops is \(\frac{N (N + 1)}{2} + 1\).

Putting it all together

We have calculated the expected number of match-ups per game to be \(2 N - 1\). We have calculated the expected number of hops per game to be \(\frac{N (N + 1)}{2} + 1\). So, from our first Proposition, the number of seconds per game is

\[ \begin{align*} \EE[\text{total time in seconds}] &= \EE[\text{# of hops}] + \frac{3}{2} \EE[\text{# of match-ups of rock-paper-scissors}] \\ &= \frac{N (N + 1)}{2} + 1 + \frac{3}{2} (2 N - 1) = \frac{N^2 + 7 N - 1}{2}. \end{align*} \]

When there are \(N = 8\) hoops, the game will last for an expected value of \(1 + 36 + \frac{3}{2} \cdot 15 = 59.5\) seconds.

To fill a \(30\)-minute gym class, which is \(1800\) seconds, you need either \(56\) or \(57\) hoops, depending on how desperately you need to fill every second. If you use \(N = 56\) hoops, you fill an expected value of \(1764.5\) seconds, while with \(N = 57\) hoops, you fill \(1823.5\) seconds.

In the video, I counted \(N = 29\) hoops. With our assumptions, the game would last an expected value of \(526.5\) seconds, which is \(8\) minutes, \(46.5\) seconds.