IRL_ABooklet_2023

We can represent the scoreboard by a $2\times n$ binary matrix, e.g., $$\left[\begin{array}{cccc}0& 1& 0& 1\\ 0& 0& 1& 1\end{array}\right].$$ The problem is then asking for the number of $2\times n$ binary matrices such that, for every $1\le t\le n$, the first $t$ elements in the first row always contain at least as many 1s as the first $t$ elements in the second row. Denote the number of possible $2\times n$ scoreboards by $T_n$. We will develop a recursion for $T_n$. First, we have $T_1=3$, as the possible $2\times 1$ scoreboards are $$\left[\begin{array}{c}0\\ 0\end{array}\right]\left[\begin{array}{c}1\\ 1\end{array}\right]\left[\begin{array}{c}1\\ 0\end{array}\right].$$ Next, for any $0\le k\le n$ define $T_{n,k}$ to be the number of $2\times n$ scoreboards which satisfy the conditions of the problem such that the top row contains $k$ more 1s than the bottom row. When $k<0$ or $n<k$, we define $T_{n,k}=0$. We then have $T_n={\sum }_k{T}_{n,k}$. From the above list of $2\times 1$ scoreboards we find $$T_{1,0}=2\text{and}{T}_{1,1}=1.$$ For $n\ge 1$ and any $k\ge 0$ we have $$T_{n+1,k}=T_{n,k-1}+2T_{n,k}+T_{n,k+1}(9)$$ where the first term on the RHS is obtained by adding $[\begin{array}{c}1\\ 0\end{array}]$ to the existing $2\times n$ scoreboard if $T_{n,k-1}\ne 0$, the second term on the RHS is obtained by adding $[\begin{array}{c}0\\ 0\end{array}]$ or $[\begin{array}{c}1\\ 1\end{array}]$ to the existing $2\times n$ scoreboard if $T_{n,k}\ne 0$, and the third term on the RHS is obtained by adding $[\begin{array}{c}0\\ 1\end{array}]$ to the existing $2\times n$ scoreboard if $T_{n,k+1}\ne 0$. The recursion (9) is even correct for $n=0$ if we set $T_{0,0}=1$.

Adding equations (9) for $0\le k\le n+1$, we obtain $$\sum _{k=0}^{n+1}{T}_{n+1,k}=4\sum _{k=0}^n{T}_{n,k}-T_{n,0},(10)$$ which, using the observation that $T_n={\sum }_{k=0}^n{T}_{n,k}$, yields $$T_{n+1}=4T_n-T_{n,0}\text{for }n\ge 1.(11)$$ We can now proceed in two different ways. The first way is a brute force calculation modulo 8 for which we use (9) and $T_n={\sum }_{k=0}^n{T}_{n,k}$:

$T_{n,k}$	$k$
$n$	0	1	2	3	4	5	6	7	8	9	10	$T_n$
0	1												1
1	2	1											3
2	5	4	1										2
3	6	6	6	1									3
4	2	0	3	0	1								6
5	4	5	6	4	2	1							6
6	5	4	5	0	1	4	1						4
7	6	2	6	6	6	2	6	1					3
8	6	0	4	0	4	0	7	0	1				6
9	4	2	0	0	0	3	6	0	2	1			2
10	2	0	2	0	3	4	7	0	5	4	1		4

From this table we see that $T_{10}\equiv 4(\mathrm{mod}8)$, which is the required result.

A second way is to prove that $T_{n,0}$ is the $(n+1)$-th Catalan number, i.e., $$T_{n,0}=C_{n+1}=\frac{1}{n+2}\left(\genfrac{}{}{0ex}{}{2n+2}{n+1}\right).$$ To show this, we describe a bijection between the set of $2\times n$ scoreboards counted by $T_{n,0}$, i.e. those which satisfy the conditions of the problem and for which the top row contains the same number of 1s as the bottom row, and the set of North-East lattice paths (also known as Dyck paths or mountain ranges if rotated by 45°) in the plane from $(0,0)$ to $(n+1,n+1)$ not going below the line $y=x$ where “North” is the step $(0,1)$ and “East” is the step $(1,0)$. To do this, we transform such a $2\times n$ scoreboard into a North-East lattice path via the following procedure: we start with a North step from $(0,0)$ and then read each subsequent pair of steps from the next column of the scoreboard, using the conventions that (a) first we perform the step for the top row element, where a 1 in the top row corresponds to a North step and a 0 in the top row corresponds to an East step, and (b) then we perform the step for the bottom row element, where a 1 in the bottom row corresponds to an East step and a 0 in the top row corresponds to a North step. At the end, we perform a final East step to end at the point $(n+1,n+1)$. It is easily checked that the generated paths are precisely the North-East lattice paths in the plane from $(0,0)$ to $(n+1,n+1)$ not going below the line $y=x$, which are counted by the $(n+1)$-th Catalan number $C_{n+1}$. Equivalently and equally well-known is that the Catalan number $C_n$ counts the number of so-called Dyck Words of length $2n$. A Dyck Word based on the two letters $N$ and $E$ is a string of length $2n$ that consists of $n$ letters $N$ and $n$ letters $E$, such that no initial segment has more $E$'s than $N$'s. The Dyck Word of the above example would be $NENNNNEENEE$ and from the procedure described above it is clear how Dyck Words correspond to the scoreboards we consider. Equation (11) now turns into $$T_{n+1}=4T_n-C_{n+1}\text{for }n\ge 1.$$ This is valid for $n=0$ as well, since $T_1=3=4-C_1=4T_0-C_1$. A straightforward induction then shows that $$T_n=4^n-\sum _{j=0}^{n-1}{4}^j{C}_{n-j},\text{for every }n\ge 1.$$ The statement of the problem follows since $C_{10}+4C_9=16796+4\cdot 4862$ is divisible by 4 but not by 8.

---

Alternative solution.

It is convenient to split each round into two throws, with Caitlin throwing before Donal. For $k\ge 1$ we let $c(2k-1)\in \{0,1\}$ be the score of Caitlin at throw $2k-1$ and $d(2k)\in \{0,1\}$ be the score of Donal at throw $2k$. The first column of the scoreboard contains $c(1)$ and $d(2)$ and, more generally, column $k$ contains $c(2k-1)$ and $d(2k)$. Finally, the total scores after $t$ throws are $C(t)={\sum }_{i=1}^{t}c(i)$ for Caitlin and $D(t)={\sum }_{i=1}^{t}d(i)$ for Donal, where we understand that $c(2k)=d(2k-1)=0$. We define a sequence $W_t$ for $t\ge 0$ by letting $W_0=0$ and, for $t\ge 1$, $$W_t=\{\begin{array}{ll}2(C(t)-D(t))& \text{if }t\equiv 0(\mathrm{mod}2)\\ 2(C(t)-D(t))-1& \text{if }t\equiv 1(\mathrm{mod}2)\end{array}$$ By inspecting all possibilities, it is easy to see that $|W_t-W_{t-1}|=1$ for all $t\ge 1$ and that $$W_t-W_{t-1}=\{\begin{array}{ll}+1& \text{if }t\text{ is odd and }c(t)=1,\text{ or }t\text{ is even and }d(t)=0\\ -1& \text{if }t\text{ is odd and }c(t)=0,\text{ or }t\text{ is even and }d(t)=1.\end{array}$$ This implies that the scoreboard is completely determined by the sequence of differences $(W_t-W_{t-1}{)}_{t\ge 1}$. We note also that $|W_t|\le t$ for all $t\ge 0$ and that $W_t\equiv t(\mathrm{mod}2)$. Comparing with Solution 1, we note that the Dyck Words mentioned there turn into the sequence $(W_t-W_{t-1}{)}_{t\ge 1}$ by removing the starting N and the trailing E, and then replacing N by +1 and E by -1. When we plot the points $(t,W_t)$ for $0\le t\le 2n$ and connect neighbours by a straight line segment, we obtain a mountain range that is obtained from the North-East lattice path in Solution 1 by removing the initial North step and the terminal East step. For this reason, we will speak about paths when we deal with sequences $(W_t{)}_{1\le t\le T}$. $$n=4\left[\begin{array}{cccc}0& 1& 0& 1\\ 0& 0& 1& 1\end{array}\right]\begin{array}{cccccccccc}t& 0& 1& 2& 3& 4& 5& 6& 7& 8\\ W_t& 0& -1& 0& 1& 2& 1& 0& 1& 0\end{array}$$ There are clearly $2^T$ possible paths for the first $T$ throws, because we can choose the differences $W_t-W_{t-1}$ freely from $\{-1,1\}$. We say a path is feasible if $W_t\ge 0$ for all even $t$ between 0 and $T$ inclusive, which is the criterion in the question. That is the same as requiring $W_t\ge -1$ for all (odd or even) $0\le t\le T$, allowing for the possibility that at some even time point, Caitlin has the same score as Donal, misses a throw and then Donal also misses.

For $T\ge 0$ and $x\in \mathbb{Z}$, we define $F_{T,x}$ to be the number of feasible paths between 0 and $T$ such that $W_T\ge x$. These are paths that start at (0, 0) and end at (T, y) for some $y\ge x$. Note that $F_{T,x}=F_{T,-1}$ for all $x\le -1$ and $F_{T,x}=0$ for $T<x$ since $|W_T|\le T$. Note also that we always have $y\equiv T(\mathrm{mod}2)$, hence $F_{T,x}=F_{T,x-1}$ if $x\equiv T(\mathrm{mod}2)$. The relationship to $T_{n,k}$ and $T_n$ from Solution 1 is $$F_{2n,2r}=\sum _{k=r}^n{T}_{n,k}\text{and}{F}_{2n,0}=T_n.(12)$$ The question requires us to show that $$F_{20,0}\equiv 4(\mathrm{mod}8).$$ We will proceed in two different ways from here. The first way will be based on a recurrence relation for $F_{t,x}$. From the definition it is clear that $$F_{0,x}=\{\begin{array}{ll}1& \text{if }x\le 0\\ 0& \text{if }x>0.\end{array}$$ For $t>0$ and $x\ge -1$ satisfying $x\equiv t(\mathrm{mod}2)$ we have $$F_{t,x}=F_{t-1,x-1}+F_{t-1,x+1}.(13)$$ To see this, recall that $F_{t,x}$ counts feasible paths for which $W_t\ge x$. The most recent throw could either have contributed +1 (in which case $W_{t-1}\ge x-1$) or -1 (in which case $W_{t-1}\ge x+1$). The claim is the sum of these two cases. Note that when $t$ is odd and $x=-1$ equation (13) reads $F_{t-1}=2F_{t-1,0}$, because $F_{t-1,-2}=F_{t-1,-1}=F_{t-1,0}$ as observed above. This is in line with the observation that, for feasible paths, $W_{t-1}\ge -2$ actually means $W_{t-1}\ge 0$ when $t$ is odd. Equation (13) is required only for even $t$, so we may use the double-step relation for $t\ge 1$ and $x\ge 0$: $$F_{2t,2x}=F_{2t-2,2x-2}+2F_{2t-2,2x}+F_{2t-2,2x+2},(14)$$ obtained from applying equation (13) twice. Using (12), this can be seen to be equivalent to the recurrence equation (9) from Solution 1. For $x=0$ equation (14) becomes $$F_{2t,0}=3F_{2t-2,0}+F_{2t-2,2},$$ because $F_{2t-2,-2}=F_{2t-2,0}$ as explained above. One possibility to finish now is to calculate $F_{20,0}(\mathrm{mod}8)$ using (14):

$F_{2t,2x}$	0	2	4	6	8	10
0	1
2	3	1
4	2	5	1
6	3	5	7	1
8	6	4	4	1	1
10	6	2	5	7	3	1
12	4	7	3	6	6
14	3	5	3	5
16	6	0	0
18	2	6
20	4

The number 4 in the bottom row of the table proves the result.

A second way to finish the solution is based on the reflection principle from the theory of random walks, instead of using a recurrence relation for $F_{t,x}$. The reflection principle can be described as follows. Let $t\ge 0$, $H<0$, and $x>H$ be integers with $t\equiv x(\mathrm{mod}2)$. Then the following are equal: The number of paths starting with $W_0=0$ and ending at $W_t=x$ having touched $H$ at least once. The number of paths starting with $W_0=0$ and ending at $W_t=2H-x$. The proof involves setting up a bijection between the two classes of path, recognising that in each case there is a first time point $\tau$ at which $W_{\tau }=H$, and reflecting each path after time $\tau$ in the horizontal line at level $H$. The usefulness of the reflection principle comes from the fact that it is easier to count the paths of the second kind. If a path starting with $W_0=0$ and ending at $W_t=2H-x$ has $u$ up steps and $d$ down steps, then $u+d=t$.

and $u-d=2H-x$. Hence, $u=(2H+t-x)/2=H+\frac{t-x}{2}$. Such a path is determined by the position of the up steps, hence their number is equal to the binomial coefficient $$\left(\genfrac{}{}{0ex}{}{t}{u}\right)=\left(\genfrac{}{}{0ex}{}{t}{H+\frac{t-x}{2}}\right).$$ The reflection principle implies that this number is also equal to the number of paths starting with $W_0=0$ and ending at $W_t=x$ having touched $H$ at least once. Subtracting this from the number of all paths ending at $W_t=x$, which is equal to $\left(\genfrac{}{}{0ex}{}{t}{(t-x)/2}\right)$, we obtain that the number of paths that start at $W_0=0$, end at $W_t=x$, and for which $W_s>H$ for all $0\le s\le t$, is equal to $$\left(\genfrac{}{}{0ex}{}{t}{\frac{t-x}{2}}\right)-\left(\genfrac{}{}{0ex}{}{t}{H+\frac{t-x}{2}}\right).$$ In particular, taking $H=-2$ and $x=t-2k$, this expression becomes $$\begin{array}{rl}\left(\genfrac{}{}{0ex}{}{t}{k}\right)-\left(\genfrac{}{}{0ex}{}{t}{k-2}\right)& =\left(\left(\genfrac{}{}{0ex}{}{t}{k}\right)+\left(\genfrac{}{}{0ex}{}{t}{k-1}\right)\right)-\left(\left(\genfrac{}{}{0ex}{}{t}{k-1}\right)+\left(\genfrac{}{}{0ex}{}{t}{k-2}\right)\right)\\ & =\left(\genfrac{}{}{0ex}{}{t+1}{k}\right)-\left(\genfrac{}{}{0ex}{}{t+1}{k-1}\right).\end{array}$$ This is the number of paths reaching $W_t=x$ without touching $-2$, which are exactly the feasible paths. Counting the feasible paths ending at $W_t\ge t-2k$ and subtracting those ending at $W_t\ge t-2k+2$ we have $$F_{t,t-2k}-F_{t,t-2k+2}=\left(\genfrac{}{}{0ex}{}{t+1}{k}\right)-\left(\genfrac{}{}{0ex}{}{t+1}{k-1}\right).(15)$$ Because $F_{t,t+2}=0$, using a telescoping sum that involves equation (15) for $k$ replaced successively by $k,k-1,k-2,\dots ,0$, we obtain $$F_{t,t-2k}=\left(\genfrac{}{}{0ex}{}{t+1}{k}\right)(16)$$ for $t\ge 0$ and integers $k\le (t+1)/2$. Substituting $t=20$ and $k=10$ gives $$F_{20,0}=\left(\genfrac{}{}{0ex}{}{21}{10}\right)=\frac{21!}{10!11!}.$$ It is sufficient to show that $v_2(F_{20,0})=2$, where $v_2(x)$ is the 2-adic valuation, that is, the highest power of 2 dividing $x$. With the aid of Legendre's formula, $v_p(n!)={\sum }_{i\ge 1}\lfloor \frac{n}{p^i}\rfloor$, this can be calculated as $$v_2\left(\frac{21!}{10!11!}\right)=v_2(21!)-v_2(10!)-v_2(11!)=18-8-8=2.$$

Alternatively, after some numerical work, one may spot formula (16) directly. With the aid of the recurrence (13), this formula can be proved by induction. When $t=0$, after recalling that $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=0$ for negative $k$, formula (16) is clear by definition for all $k\le 0$. For $t\ge 1$, using (13), we obtain $$F_{t,x}=F_{t-1,x-1}+F_{t-1,x+1}=\left(\genfrac{}{}{0ex}{}{t}{(t-x)/2}\right)+\left(\genfrac{}{}{0ex}{}{t}{(t-x)/2-1}\right)=\left(\genfrac{}{}{0ex}{}{t+1}{(t-x)/2}\right)$$ $$F_{t,-1}=2F_{t-1,0}=2\left(\genfrac{}{}{0ex}{}{t}{(t-1)/2}\right)=\left(\genfrac{}{}{0ex}{}{t}{(t-1)/2}\right)+\left(\genfrac{}{}{0ex}{}{t}{(t+1)/2}\right)=\left(\genfrac{}{}{0ex}{}{t+1}{(t+1)/2}\right).$$ This concludes the proof of formula (16) by induction.