This Riddler puzzle is a shout-out to this YouTube video of a game called “Hoop hop showdown”.

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?

Here is a derivation of how I solved the problem:

[Show Solution]

**Note:** The wording in the problem is a bit ambiguous with regards to a few details. e.g. Do the players start outside and jump into the first hoop when they start or do they start inside the first hoop? Does the game end when you win at the last hoop, or one second later when you jump out? I made assumptions that I thought were reasonable in formulating the problem. While slight changes in details regarding the problem could change the final answer, the same general solution approach should still apply.

There are $N$ hoops but there are $k=1,2,\dots,2N-1$ possible ways in which two kids can stop to have a rock-paper-scissors (RPS) match. This is because the two kids can land in the same hoop or in adjacent hoops. Here is a diagram for $N=3$ showing all possible pairs:

Here is an example of how the game might play out in this simple scenario:

- When the game starts, both kids are outside the hoops. After 2 seconds, we end up in the $k=3$ case.
- Suppose blue wins. Then 1 second later we are in $k=5$.
- Suppose orange wins. Then 1 second later we are in $k=2$.
- Suppose orange wins. Then 1 second later we are in $k=1$.
- Suppose orange wins. Then the game ends.

Let’s generalize this process to any number of hoops. We’ll call $f(k)$ the expected number of seconds we have to wait for the game to end if we are currently in state $k$. If we are at state $k$, here are the options:

- If orange wins RPS, the next showdown occurs at state $\left\lfloor \frac{k}{2} \right\rfloor$ after $\left\lfloor \frac{k+2}{4} \right\rfloor$ seconds unless $k=1$, in which case the game ends.
- If blue wins RPS, the next showdown occurs at state $\left\lfloor \frac{2N+k+1}{2} \right\rfloor$ after $\left\lfloor \frac{2N-k+2}{4} \right\rfloor$ seconds unless $k=2N-1$, in which case the game ends.

Note that we’re using the notation $\left\lfloor x \right\rfloor$ which is the floor function (round $x$ down to the nearest integer). We must also account for how many seconds a game of RPS lasts on average. Let’s call this $r$. There are nine equally likely possible games, and one third of them end in a tie (so we must play again). So the game duration satisfies: $r = 1 + \frac{1}{3}r$. In other words, we have $r=\frac{3}{2}$. Putting everything together, the function $f(k)$ satisfies:

\begin{multline}

f(k) = \frac{3}{2} + \frac{1}{2}\left( \left\lfloor \frac{k+2}{4} \right\rfloor + f\biggl(\left\lfloor \frac{k}{2} \right\rfloor\biggr) \right)\\

+ \frac{1}{2}\left( \left\lfloor \frac{2N-k+2}{4} \right\rfloor + f\biggl( \left\lfloor \frac{2N+k+1}{2} \right\rfloor \right) \biggr)

\end{multline}with the boundary conditions $f(0)=f(2N)=0$. These are in fact linear equations in the variables $f(k)$ for $k=0,1,\dots,2N$. Ultimately, we want to know the average duration of a game. The first showdown always occurs at state $N$ and is preceded by $\left\lfloor\frac{N+1}{2}\right\rfloor$ hops. So we’re ultimately looking to find:

\[

T_\text{avg} = \left\lfloor\frac{N+1}{2}\right\rfloor + f(N)

\]Here is how you would solve the problem in the $N=3$ case. The equations that relate the different $f(k)$ can be written out in matrix-vector form:

\[

\begin{bmatrix}

1 & 0 & 0 & -\tfrac{1}{2} & 0 \\

-\tfrac{1}{2} & 1 & 0 & -\tfrac{1}{2} & 0 \\

-\tfrac{1}{2} & 0 & 1 & 0 & -\tfrac{1}{2} \\

0 & -\tfrac{1}{2} & 0 & 1 & -\tfrac{1}{2} \\

0 & -\tfrac{1}{2} & 0 & 0 & 1

\end{bmatrix}

\begin{bmatrix}

f(1)\\ f(2) \\ f(3) \\ f(4)\\ f(5)

\end{bmatrix}

=\begin{bmatrix}

2\\\tfrac{5}{2}\\\tfrac{5}{2}\\\tfrac{5}{2}\\2

\end{bmatrix}

\]Solving these equations produces $f(3)=11.5$ and therefore $T_\text{avg} = 13.5\text{ sec}$. As we add more hoops (increase $N$), the procedure is analogous, and we can write code that rapidly solves these equations for a wide range of $N$ values… But we can do better!

Note that we don’t actually care about the other values of $f(k)$. We only need to know the middle one, $f(N)=f(3)$. Also note that the columns of the matrix all sum to zero except the middle one… So if we sum all columns (equivalent to summing all our equations together), we obtain:

\[

f(3) = 2+\tfrac{5}{2}+\tfrac{5}{2}+\tfrac{5}{2}+2 = 11.5

\]which is the same answer as we found by solving the whole system! In fact, this pattern persists for all $N$. Our matrix will always have dimensions $(2N-1)\times(2N-1)$ and all columns will sum to zero except the middle one! So in general, we can write the solution for the case of $N$ hoops as:

\begin{align}

T_\text{avg} &= \left\lfloor\frac{N+1}{2}\right\rfloor + f(N) \\

&= \left\lfloor\frac{N+1}{2}\right\rfloor+\sum_{k=1}^{2N-1} \left( \frac{3}{2} + \frac{1}{2}\left\lfloor \frac{k+2}{4} \right\rfloor + \frac{1}{2}\left\lfloor \frac{2N-k+2}{4} \right\rfloor \right) \\

&= \frac{3}{2}(2N-1) + \left\lfloor\frac{N+1}{2}\right\rfloor+\sum_{k=1}^{2N-1} \left( \frac{1}{2}\left\lfloor \frac{k+2}{4} \right\rfloor + \frac{1}{2}\left\lfloor \frac{2N-k+2}{4} \right\rfloor \right) \\

&= \frac{3}{2}(2N-1) + \sum_{k=1}^{2N} \left\lfloor \frac{k+2}{4} \right\rfloor \\

&= \frac{3}{2}(2N-1) + \sum_{m=1}^{N} \left( \left\lfloor \frac{2m+1}{4} \right\rfloor + \left\lfloor \frac{2m+2}{4} \right\rfloor \right) \\

&= \frac{3}{2}(2N-1) + \sum_{m=1}^{N} m \\

&= \frac{3}{2}(2N-1) + \frac{1}{2}N(N+1) \\

&= \frac{1}{2}(N^2+7N-3)

\end{align}The simplification in the third last step follows by letting $m = 2q+r$ where $r\in\{0,1\}$. Then we may write:

\begin{align}

\left\lfloor \frac{2m+1}{4} \right\rfloor + \left\lfloor \frac{2m+2}{4} \right\rfloor

&=\left\lfloor \frac{4q+2r+1}{4} \right\rfloor + \left\lfloor \frac{4q+2r+2}{4} \right\rfloor \\

&=2q+\left\lfloor \frac{2r+1}{4} \right\rfloor + \left\lfloor \frac{2r+2}{4} \right\rfloor\\

&=2q+r\\

&=m

\end{align}

And if you just want to see the solutions:

[Show Solution]

The average duration (in seconds) of a game of Hoop hop showdown is given by:

$\displaystyle

T_\text{avg} = \frac{1}{2}(N^2+7N-3)

$

Here is a plot showing the expected duration of the game as a function of the number of hoops.

So we need about 57 hoops in order to ensure that the average duration of a game of game of Hoop hop showdown lasts 30 minutes.

I had a different interpretation of the last segment. Assumed there would be one additional RPB battle after Orange wins your k=1 case and then one more second to jump to victory. My answer: Tavg = N^2+7N+1 seconds. This results in N=8, 121 secs. N=39, 30 mins (minus 5 secs). General approach still the same, but very different answers to the 538 Riddler question.

Hi Laurent,

I like your solution — I got almost the same except I stupidly solved the linear algebra instead of summing the columns and therefore found the algebraic form only by looking-at-answers.

But I think your answer is too large by one factor of 3/2 and should be (N^2 + 7 N – 3)/2. I think you double-count the first RSP game, since you count the game once in f(k) and once in T_{avg}.

To see this quickly, consider N=1. The players hop to the middle (1 sec) and play RSP (3/2 sec). The winner has won the game, so that took 5/2 sec. But your formula gives 4 sec.

Great catch, you’re absolutely right. I fixed it in my write-up. Thanks!

This depends on your interpretation of whether there is a final RPS challenge before jumping out of the last hoop and whether the last jump takes another second. If yes, I still think N=3 hoops would require an avg T = 31 secs and in general Tavg = N^2+7N+1. The illustration under the puzzle appears to support this view.

I wasn’t able to glean much from that illustration… and the description in the wording of the problem is ambiguous/incomplete. I guess we’ll just have to wait and see how Oliver intended the problem to be interpreted!

Looks like your interpretation was right. Congrats again for the call out in the solution!

What about the diameter of the hoop? ??

my question too. 24, 30 or 36″? or does it matter?

Hi Laurent,

Thank you for your nice description of your solutions, I am learning a lot.

I have only difficulties with how you simplify your expressions, could you please elaborate little bit more about how you were simplifying that Tavg expression?

Thank you.

Sure, would be happy to elaborate. The trickiest part is the fourth-to-last line where

\[

\left( \left\lfloor \frac{2m+1}{4} \right\rfloor + \left\lfloor \frac{2m+2}{4} \right\rfloor \right)

\] is simplified to $m$. I have an additional explanation of that step right after the derivation. If there is a specific part you’re struggling with, just let me know and I can elaborate on it.

I didn’t understand how you got from line 3 to 4, than how you got to to line 5 with m variable.

That simplification from 5 to 6 is very nice, only I don’t get how you introduced that m = 2q+r.

Thank you.