Hoop hop showdown

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:

1. When the game starts, both kids are outside the hoops. After 2 seconds, we end up in the $k=3$ case.
2. Suppose blue wins. Then 1 second later we are in $k=5$.
3. Suppose orange wins. Then 1 second later we are in $k=2$.
4. Suppose orange wins. Then 1 second later we are in $k=1$.
5. 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:

1. 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.
2. 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}

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.