nivotko

Surjective Clock Sequence

The following analog clock has two hands that can move independently of each other.

Initially, both hands point to the number $12$ . The clock performs a sequence of hand movements so that on each movement, one of the two hands moves clockwise to the next number on the clock while the other hand does not move.

Let $N$ be the number of sequences of 144 hand movements such that during the sequence, every possible positioning of the hands appears exactly once, and at the end of the 144 movements, the hands have returned to their initial position. Find the remainder when $N$ is divided by $1000$ .

Discussion.

The problem is from AIME 2023, number 14. I think this is one of the most beautiful problem in the contest.

We represent the state of the clock as a point $(x,y)$ where $x$ represents the number pointed by shorter hand and $y$ represents the number pointed by longer hand. At each step, from $(x,y)$ , the clock can go to either $(x+1,y)$ or $(x,y+1)$ . Consider the value of $x$ and $y$ as modulo $12$ , meaning that $12 = 0$ .

Hence all the states are collected in a set $S=\{(x,y): 0 \le x,y \le 11\}$ . We want to look for the number of paths that visit every point in $S$ exactly once where in each step we can either move up or to the right one unit; and if we are at the border, that is when $x=11$ or $y=11$ we go back to $x=0$ or $y=0$ if we move to the right or move up, respectively (think of this as a circular board).

Let us define $S_k=\{(x,y) \in S: x+y \equiv k \pmod{12}\}$ for $k=0,1,\dots,11$ . Let $P_0=(0,0),P_1,P_2,\dots,P_{143}$ be the path. Note that if $P_i=(x,y)$ , then $P_{i+1}$ is either $(x+1,y)$ or $(x,y+1)$ . This means, if $P_i \in S_j$ , then $x+y \equiv j \pmod{12}$ and thus $x+y+1 \equiv j+1 \pmod{12}$ , meaning that $P_{i+1} \in S_{j+1}$ . Since $P_0 \in S_0$ we have that $P_n \in S_{n \pmod{12}}$ for every $n \ge 1$ .

Now, suppose that in the path, at point $P_k=(x,y)$ we go to the right, say $P_{k+1}=(x+1,y)$ . Consider point $(x+1,y-1)$ . Note that $P_{k'}=(x+1,y-1)$ for some $k' \ne k$ . Note that from $P_{k'}$ we cannot go up since then we visit $P_{k+1}$ from $P_{k}$ and $P_{k'}$ which is absurd since we want every vertex to be contained exactly once in $P_0,\dots,P_{143}$ . Hence, from $P_{k}$ we must also go to the right. Note that if $(x,y)$ goes to the right, then $(x+1,y-1)$ must also go to the right. By induction, we have that for every $(a,b)$ with $a+b \equiv x+y \pmod{12}$ must also go to the right.

Similarly, we can prove that if the path goes up from $(x,y)$ , then the path also goes up for $(x-1,y+1)$ . By induction, we have that for every $(a,b)$ with $a+b \equiv x+y \pmod{12}$ , the path from $(a,b)$ also goes up.

This means that for each $j=0,1,\dots,11$ , the path must make the same direction from each point in $S_j$ (the $12$ edges leaving vertices in $S_j$ are either all vertical or all horizontal). The following is an example path where every vertex is visited exactly once.

Note that the visualization above, we also show the border points $(12,y)$ and $(x,12)$ which are basically the same as $(0,y)$ and $(x,0)$ . The colored edges on the rightmost border ( $x=12$ ) are the same with the leftmost border ( $x=0$ ); similarly with $y=12$ and $y=0$ .

Now, note $P_0 \in S_0,\dots,P_{11} \in S_{11}$ and $P_{12} \in S_0$ . The move made from $P_{12}$ will be the same as the move made from $P_0$ . Moreover, the move from the $12$ points $P_0,P_{12},\dots,P_{132}$ will be all horizontal or all vertical. More generally, for each $i=0,1,\dots,11$ , the move made from points $P_i,P_{i+12},P_{i+2 \cdot 12}, \dots, P_{i+11 \cdot 12}$ will be all horizontal or all vertical since they all belong to $S_i$ .

Suppose that from $P_0$ to $P_{12}$ we will make $a$ horizontal moves and $b$ vertical moves where $a+b=12$ and $P_{12}=(a,b)$ . Since the move pattern repeats, we must have $P_{24}=(2a,2b),\dots,P_{132}=(11a,11b)$ . Since every point must be visited exactly once, then every point $0,a,2a,\dots,11a$ must be all distinct modulo $12$ , hence $\text{gcd}(a,12)=1$ . Similarly, for $b$ , $\text{gcd}(b,12)$ . The numbers among $0,1,2,\dots,11$ that are relatively prime to $12$ is $4$ ; they are $1,5,7,11$ . Hence the number of possibility for $P_{12}$ such that every vertex is visited at most once and the path goes back to $(0,0)$ is $4$ , namely $(1,11), (5,7), (7,5)$ , and $(11,1)$ . The path pattern of horizontal/vertical is periodic for every $12$ steps, so we just need to focus on how many ways we can go to $(0,0)$ to one of $(1,11), (5,7), (7,5)$ , and $(11,1)$ , in which at each step we go to right or go up. The number of such paths is then $\displaystyle {12 \choose 1}+{12 \choose 5}+{12 \choose 7} + {12 \choose 11} = 12 + 792 + 792 + 12 = 1608$ . So $N=1608$ and its last three digits is $608$ .

Dynamic Programming of Binge Watching Happiness

Let $A[1\dots n]$ be an array consisting of positive integers and $T$ be a positive integer.

source: https://universe.byu.edu/2018/01/30/binge-watching-tv-associated-with-poor-health-habits1/

For a holiday of $n$ days, George plans to watch movies in a streaming service at most one movie each day. On day $i \in \{1,2,\dots,n\}$ , if he watches the movie, he will feel happy and the value of that happiness will be $A[i]$ . Binge watching movies everyday can be tiring mentally so he wants to make sure he gets enough rest and keeps track of boredom score $K$ . Initially, the boredom score is $K=0$ . He wants to make sure that his boredom score never exceeds $T$ , i.e. $K \le T$ , during the holiday; hence, when $K=T$ , George do not watch a movie. If he watches a movie on a day, his boredom score increases by one. Otherwise, his boredom score decrements if $K>0$ and stays zero if $K=0$ (the boredom score can never be negative).

Find the maximum sum of happiness that George can have during the $n$ days.

Discussion.

This problem is from my friend HLN’s exam in algorithms. This can be solved using dynamic programming approach. But I will not discuss how to do its dynamic programming approach, but rather its recursive approach; since dynamic programming is just an recursive algorithm with less redundancy.

Let us define function $\texttt{solve(i, k)}$ as the maximum value that George can get from $A[i...n]$ given that his boredom score after day $i-1$ is $k$ .

The base case is when $i=n$ . If $i=n$ and $k=T$ , George cannot watch a movie, hence giving happiness $0$ . If $i=n$ and $k<T$ , George can watch movie on day $n$ and gets happiness score $A[n]$ .

This is how it looks like in Python:

t=2
a=[1,2,3,4,5,6]

def solve(i, k): 
  if i == len(a)-1:
    if k==t:
      return 0
    else:
      return a[-1]

Now, suppose $i<n$ . If $k=T$ , George cannot watch movie on day $i$ . So he will rest on day $i$ and on the next day his boredom score will decrease by one if $k>0$ and stay $0$ if $k=0$ . Hence, the function will just return $\texttt{solve(i+1,k-1)}$ if $k>0$ and $\texttt{solve(i+1,0)}$ if $k=0$ .

Now, if $k<T$ , George has two choices: watch movie on day $i$ or not. If he chooses to watch movie on day $i$ , he will get happiness score $A[i]$ but his boredom score will increase by one on the next day. Hence, we return $A[i]+\texttt{solve(i+1,k+1)}$ . If George chooses not watch on day one, he will not get happiness score, but his boredom score will decrease by one on the next day if $k>0$ and stay $0$ if $k=0$ , i.e. our function returns $\texttt{solve(i+1,k-1)}$ or $\texttt{solve(i+1,0)}$ if $k>0$ and $k=0$ , respectively. Under this two possible choices of watching or not, George will choose the one that maximizes his overall happiness.

Completing the Python code above, the definition of $\texttt{solve(i,k)}$ can be seen below:

def solve(i, k): 
  if i == len(a)-1:
    if k==t:
      return 0
    else:
      return a[-1]
  if k<t:
    c1 = a[i] + solve(i+1,k+1)
    c2 = 0
    if k>=1:
      c2 = solve(i+1,k-1)
    else:
      c2 = solve(i+1,0)
    if c1<c2:
      return c2
    else:
      return c1
  else:
    if k==0:
      return solve(i+1,0)
    else:
      return solve(i+1,k-1)

The execution of our algorithm above on some instances:

$\texttt{t=1}$ and $\texttt{a=[1,2,3,4,5,6]}$ gives maximum happiness $12$
$\texttt{t=1}$ and $\texttt{a=[1,2,10,4,5,6]}$ gives maximum happiness $17$
$\texttt{t=2}$ and $\texttt{a=[1,2,3,4,5,6]}$ gives maximum happiness $15$ .

Next challenge is to implement this algorithm using tables so that no redundancy is called. The dynamic programming approach will need to store the results in an $\Theta(n) \times \Theta(T)$ array where each cell can be filled in $\Theta(1)$ time. Hence the complexity of this algorithm will be $\Theta(nT)$ .

You can find the colab here.

I hope you enjoy this problem!

Canadian inequality 1979

Let $a$ and $b$ be positive real numbers. Let $A_1,A_2,G_1,G_2$ be positive real numbers such that $a,A_1,A_2,b$ is an arithmetic progression and $a, G_1,G_2,b$ is a geometric progression. Show that $A_1A_2 \ge G_1 G_2$ .

We also have $aG_2=G_1^2$ and $G_1b=G_2^2$ . Multiplying both equations, we have $abG_1G_2=G_1^2G_2^2$ , meaning $G_1G_2=ab$ .

Now, WLOG $b\ge a$ and let $d=\dfrac{b-a}{3} \ge 0$ . We know that $A_1=a+d$ , $A_2=a+2d$ , and $b=a+3d$ .

We need to show that $(a+d)(a+2d) \ge a(a+3d)$ .

Multiplying the terms, we have $a^2+3ad+2d^2 \ge a^2+3ad$ which is equivalent to $2d^2 \ge 0$ which is true.

Subsets with exactly one pair of consecutive integers

Find the number of subsets of $\{1,2,3,\dots,10\}$ that contains exactly one pair of consecutive integers.

Let $T_k$ be the number of subsets of $\{m+1,m+2,\dots,m+k\}$ that does not contain consecutive integers. Note that the choice of $m$ is not relevant here. If $m+1$ is included in the subset, then $m+2$ must not be included, hence we just need to construct the subset with no consecutive elements from $\{m+3,\dots,m+k\}$ . The number of ways to construct them is $T_{k+2}$ , by definition. Otherwise, if $m+1$ is not included, we just need to find the number of subset with no consecutive elements from $\{m+2,\dots,m+k\}$ which is $T_{k+1}$ by definition. Hence, $T_k=T_{k-1}+T_{k-2}$ for all $k \ge 2$ . We observe that $T_1=2$ , $T_2=3$ . Note that this is related to Fibonacci sequence. We can see that $T_3 =5, T_4 = 8, T_5 = 13, T_6 = 21, T_7 = 34$ .

Now, let’s go the back to the original problem. The unique pairs of consecutive integers that we can include in the subset are $(1,2), (2,3), \dots, (9,10)$ .

If $(1,2)$ is chosen, we must construct subset with no consecutive elements from $\{4,5,\dots,10\}$ . The number is $T_7$ .

If $(2,3)$ , we must construct subset with no consecutive elements from $\{5,6,\dots,10\}$ . The number is $T_6$ .

If $(3,4)$ is chosen, we must construct subset with no consecutive elements from $\{1\}$ as well as from $\{6,7,\dots,10\}$ . Note that we can pair them up. So the number of ways is $T_1 \times T_5$ .

If $(4,5)$ is chosen, we must construct subset with no consecutive elements from $\{1,2\}$ as well as from $\{7,8,9,10\}$ . The number of ways is $T_2 \times T_4$ .

If $(5,6)$ is chosen, we must construct subset with no consecutive elements from $\{1,2,3\}$ as well as from $\{8,9,10\}$ . The number of ways is $T_3 \times T_3$ .

For $(6,7)$ up to $(9,10)$ , the condition is symmetrical.

Hence, the number of subsets of $\{1,2,\dots,10\}$ that contains exactly one consecutive pair is $2(34 + 21 + 2 \times 13 + 3 \times 8) + 5 \times 5 = 235$ .

Comments. The problem of determining the number of subsets with no consecutive elements is a well-known problem among mathematics olympiad community. So this problem is quite disappointing to be placed at question 11 because it gives huge advantage to students who know about this problem before (the remaining is just working out cases as presented above).

Nice divisibility property of sequence

Let $a_1,a_2,\dots$ be an infinite sequence of positive integers such that $k+\ell$ divides $a_k+a_\ell$ for all positive integers $k$ and $\ell$ . Show that $k-\ell$ divides $a_k-a_\ell$ for all positive integers $k$ and $\ell$ such that $k>\ell$ .

Polish Mathematical Olympiad 2023

The following solution is credited to Tintarn on MATHLINKS.

Let $d=k-\ell$ for any $k>\ell$ . Consider a positive integer $n$ such that $d|n+k$ . Consequently $d|n+d+\ell$ meaning $d|n+\ell$ .

Finally, since $d|a_n+a_k$ and $d|a_n+a_\ell$ , we have that $d|(a_n+a_k)-(a_n+a_\ell)$ , meaning $k-\ell|a_k-a_\ell$ .

Moment of uniform distribution

A uniform distribution on interval $[a,b]$ is described by a probability density function (pdf) $\displaystyle f_X(x)=\dfrac{x-a}{b-a}$ .

We want to compute $E[X^t]$ , the $t-$ th moment of $X$ .

As usual, we look at the generating function

$\displaystyle E[e^{zX}] = \sum_{k=0}^\infty \dfrac{z^k}{k!} E[X^k]$ .

Note that

$\displaystyle E[e^{zX}] = \int_a^b e^{zx} \dfrac{1}{b-a} \text{d}x = \dfrac{1}{b-a} \left[ \dfrac{1}{z}e^{zx} \right]_a^b = \dfrac{e^{bz}-e^{az}}{z(b-a)}$

$\displaystyle = \dfrac{1}{z(b-a)}\sum_{k=0} \dfrac{b^k-a^k}{k!}z^k = \dfrac{1}{1!} + \dfrac{b^2-a^2}{b-a} \cdot \dfrac{1}{2!} z + \dfrac{b^3-a^3}{b-a} \cdot \dfrac{1}{3!}z^2 + \dots$ .

Hence,

$\dfrac{E[X^t]}{t!} = \dfrac{b^{t+1}-a^{t+1}}{b-a} \cdot \dfrac{1}{(t+1)!}$

$E[X^t] = \dfrac{1}{t+1} \cdot \dfrac{b^{t+1}-a^{t+1}}{b-a}.$

We can see that $E[X] = \dfrac{1}{2} \cdot \dfrac{b^2-a^2}{b-a}=\dfrac{b+a}{2}$ . Moreover, $E[X^2]=\dfrac{1}{3} \cdot \dfrac{b^3-a^3}{b-a}=\dfrac{b^2+ba+a^2}{3}$ and hence $\text{Var}(X) = E[X^2]-E[X]^2 = \dfrac{b^2+ba+a^2}{3}-\dfrac{b^2+2ba+a^2}{4}=\dfrac{b^2-2ba+a^2}{12}=\dfrac{(b-a)^2}{12}$ .

Exponential distribution and generating function

An exponential distribution $X \sim \text{Exp}(\lambda)$ is described by a probability density function (pdf)

$f_X(x) = \lambda e^{-\lambda x}$ for all $x \ge 0$ .

We would like to compute its $t-$ th moment, namely $E[X^t]$ .

Let $z$ be a constant and consider the random variable $e^{zX}$ .

Note that, we can expand this as follows:

$\displaystyle e^{zX} = \sum_{k=0}^\infty \dfrac{z^k}{k!} X^k$

and by the linearity of expectation,

$\displaystyle E[e^{zX}] = \sum_{k=0}^\infty \dfrac{z^k}{k!}E[X^k]$ .

Hence, we have that

$\displaystyle E[e^{zX}] = \int_0^\infty e^{zx}f_X(x) \text{d}x$

$\displaystyle E[e^{zX}] = \int_0^\infty \lambda e^{(z-\lambda)x} \text{d}x$

Setting $u=(z-\lambda)x$ , maka $\text{d}u = (z-\lambda) \text{d}x$ , and we obtain

$\displaystyle E[e^{zX}] = \int_0^{-\infty} \dfrac{\lambda }{z-\lambda} e^u \text{d}u = \dfrac{\lambda}{\lambda - z}$ .

But then, we know that by expanding $\dfrac{\lambda}{\lambda -z}$ ,

$\displaystyle E[e^{zX}] = \dfrac{1}{1-\dfrac{z}{\lambda}} = \sum_{k=0}^\infty \dfrac{z^k}{\lambda^k}.$

By matching coefficients, we obtain

$\displaystyle \dfrac{E[X^k]}{k!} = \dfrac{1}{\lambda^k}$ ,

meaning that

$E[X^k] = \dfrac{k!}{\lambda^k}$ .

Note that this is one nice application of generating function in probability theory. Plugging in $k=1$ , we obtain $E[X] = \dfrac{1}{\lambda}$ and plugging in $k=2$ , we obtain $E[X^2]=\dfrac{2}{\lambda^2}$ , and $\text{Var}(X) = E[X^2]-E[X]^2 = \dfrac{2}{\lambda^2} - \dfrac{1}{\lambda^2} = \dfrac{1}{\lambda^2}$ .

A simple trigonometry exercise on a quadrilateral

Let there be a quadrilateral $ABCD$ such that $\angle CAD=45^\circ, \angle ACD=30^\circ, \angle BAC=\angle BCA=15^\circ$ . Find $\angle DBC^\circ$ .

The question is posed at Moldovan TST for European Girls Mathematical Olympiad (EGMO) 2023.

The diagram for the question is as follows:

Let $DBC = \theta$ and since $\angle DCB = 60^\circ$ , we also have $\angle BDC = 120^\circ - \theta$ .

By law of sines on triangle $ABC$ , we have

$\dfrac{BC}{\sin 15^\circ} = \dfrac{AC}{\sin 150^\circ}$

$BC = AC \cdot \dfrac{\sin 15^\circ}{\sin 150^\circ} \ldots (1)$

By law of sines on triangle $ADC$ , we have

$\dfrac{DC}{\sin 30^\circ} = \dfrac{AC}{\sin 105^\circ}$

$DC = AC \cdot \dfrac{\sin 30^\circ}{\sin 105^\circ} \ldots (2)$

Finally, by law of sines of triangle $BDC$ , we have

$\dfrac{BC}{\sin 120^\circ - \theta} = \dfrac{CD}{\sin \theta}$ .

Hence, by using identity $(1)$ and $(2)$ on the numerator and the denumerator, respectively, we have

$\dfrac{\sin \theta}{\sin 120^\circ - \theta} = \dfrac{BC}{CD} = \dfrac{AC \cdot \dfrac{\sin 15^\circ}{\sin 150^\circ}}{AC \cdot \dfrac{\sin 30^\circ}{\sin 105^\circ}}$

$= \dfrac{\sin 15^\circ \cdot \sin 105^\circ}{\sin 150^\circ \cdot \sin 30^\circ} = 4 \sin 15^\circ \cdot \sin 105^\circ$ .

It is easy to see that

$4 \sin 15^\circ \cdot 105^\circ = 2 \left( \cos (105^\circ - 15^\circ) - \cos(105^\circ + 15^\circ) \right) = 1$ .

Hence, we must have $\sin \theta = \sin(120^\circ - \theta)$ . The only possibility for angles of triangles to satisfy this relation is if $\theta = 120^\circ - \theta$ , meaning $\theta = 60^\circ$ .

Hence, $\angle BDC=60^\circ$ .

Does anyone find a synthetic geometrical solution to this? I believe that a nice solution usually exist because the triangle $BCD$ is eventually an equilateral triangle. 🙂

Smoothing via geometric means

Find the least real number $M$ such that for all positive real numbers $a, b, c$ , the following inequality holds:

$a+\sqrt{ab}+\sqrt[3]{abc} \le M(a+b+c)$ .

Substituting $a=16,b=4,c=1$ , we obtain

$a+\sqrt{ab}+\sqrt[3]{abc} = 16+\sqrt{16 \cdot 4} + \sqrt[3]{16 \cdot 4 \cdot 1} =28 \le M(16+4+1)=21M$ .

Hence, it must be the case that $M \ge \dfrac{28}{21}=\dfrac{4}{3}$ .

We now prove that $a + \sqrt{ab} + \sqrt[3]{abc} \le \dfrac{4}{3}(a+b+c)$ , i.e. $\dfrac{1}{3}a+\dfrac{4}{3}b+\dfrac{4}{3}c \ge \sqrt{ab}+\sqrt[3]{abc}$ .

Note that by AM-GM inequality, we have

$\dfrac{1}{4}a + b \ge 2 \sqrt{\dfrac{1}{4}ab} = \sqrt{ab}$

$\dfrac{1}{12}a + \dfrac{1}{3}b + \dfrac{4}{3}c \ge 3\sqrt[3]{\dfrac{1 \cdot 1 \cdot 4}{12 \cdot 3 \cdot 3} \cdot abc} = \sqrt[3]{abc}$ .

Summing the two inequalities, we obtain

$\dfrac{1}{3}a + \dfrac{4}{3}b + \dfrac{4}{3}c \ge \sqrt{ab} + \sqrt[3]{abc}$ ,

as desired.

Challenge. Let $n \ge 3$ be a natural number. What is the smallest constant $C$ (possibly depending on $n$ ) such that for any positive real numbers $x_1,x_2,\dots,x_n$ , the following inequality holds?

$x_1+\sqrt{x_1x_2} + \sqrt[3]{x_1 x_2 x_3} + \dots + \sqrt[n]{x_1 x_2 \dots x_n} \le C(x_1+x_2+\dots+x_n)$ .

Number of occurrences of HT in coin tosses

You toss a coin $n$ times and each toss is independent of the others. Each toss is either a head ( $H$ ) or a tail ( $T$ ). The tosses result a string of $H$ ‘s and $T$ ‘s of length $n$ . What is the expectation and the variance of the number of occurrences of $HT$ in the sequence?

Suppose that the resulting string is $s_1s_2 \dots s_n$ where $s_i \in \{H,T\}$ . Define an indicator random variable $X_i$ for $i=1,2,\dots,n-1$ such that $X_i=1$ if $s_i=H$ and $s_{i+1}=T$ ; and $X_i=0$ otherwise.

Define a random variable $X=X_1+X_2+\dots+X_{n-1}$ . From the definition, $X$ counts the number of occurrences of $HT$ in the string $s_1s_2 \dots s_n$ .

We want to compute $E[X]$ and $\text{Var}(X)$ .

First, note that $E[X_i] = p(X_i=1) \cdot 1 + p(X_i=0) \cdot 0 = p(X_i=1) = \dfrac{1}{4}$ , since $s_is_{i+1} \in \{HH,HT,TH,TT\}$ and every value is equally likely. Moreover, $\text{Var}(X_i) = E[X_i^2] - E[X_i]^2 = E[X_i] - E[X_i]^2 = \dfrac{1}{4} \cdot (1-\dfrac{1}{4}) = \dfrac{3}{16}$ . (One can also say $E[X_i] \sim \text{Bern}(\frac{1}{4})$ and use $E[X_i]=p$ and $\text{Var}(X_i) = p(1-p)$ .

To compute $E[X]$ , we have $E[X] = E[X_1+X_2+\dots+X_{n-1}] = E[X_1]+E[X_2]+\dots+E[X_{n-1}]=(n-1) \cdot \dfrac{1}{4} = \dfrac{n-1}{4}$ .

Now, we want to compute $\text{Var}(X)$ .

$\text{Var}(X) = E[X^2] - E[X]^2$

$= E[(X_1+X_2+\dots+X_{n-1})^2] - (E[X_1+X_2+\dots+X_{n-1}])^2$

$\displaystyle = E\left[ \sum_{i=1}^{n-1} X_i^2 + 2 \sum_{1 \le i < j \le n} X_iX_j \right] - \sum_{i=1}^{n-1} E[X_i]^2 - 2\sum_{1 \le i < j \le n} E[X_i]E[X_j]$

$\displaystyle = \sum_{i=1}^{n-1} (E[X_i^2] - E[X_i]^2) + 2\sum_{1 \le i < j \le n} (E[X_iX_j] - E[X_i]E[X_j])$

$\displaystyle = \sum_{i=1}^{n-1} \text{Var}(X_i) + 2 \sum_{1 \le i < j \le n} \text{Cov}(X_i,X_j)$

$\displaystyle = \dfrac{3(n-1)}{16} + 2 \sum_{i=1}^{n-2} \text{Cov}(X_i,X_{i+1}) ... (*)$

$\displaystyle = \dfrac{3(n-1)}{16} + 2 \cdot (n-2) \cdot \text{Cov}(X_1,X_2) ... (**)$

$\displaystyle = \dfrac{3(n-1)}{16} - \dfrac{2(n-2)}{16} \dots (***)$

$\displaystyle = \dfrac{n+1}{16}$ .

We clarify some equations used in the chain of equations above. For $(*)$ , note that if $|i-j|>1$ , then $X_i$ and $X_j$ are determined by four independent tosses $s_i,s_{i+1},s_j,s_{j+1}$ meaning that $X_i$ and $X_j$ are independent, i.e. $\text{Cov}(X_i,X_j)=0$ . For $(**)$ , note that $\text{Cov}(X_1,X_2)=\text{Cov}(X_2,X_3)=\dots=\text{Cov}(X_{n-2},X_{n-1})$ — this is due to each of $\text{Cov}(X_i,X_{i+1})$ are solely determined by $s_i,s_{i+1},s_{i+2}$ . For $(***)$ , note that $\text{Cov}(X_1,X_2)=E[X_1X_2]-E[X_1]E[X_2]$ . Now, we have that $X_1X_2 \in \{0,1\}$ and $p(X_1X_2 = 1)=0$ because it is impossible to have $X_1=X_2=1$ (since $X_1=1$ implies $s_2=T$ but $X_2=1$ implies $s_2=H$ ). Hence, $E[X_1X_2]=0$ . Hence, $\text{Cov}(X_1,X_2) = 0 - \dfrac{1}{4} \cdot \dfrac{1}{4}=-\dfrac{1}{16}$ , as desired.

I see this problem when I discuss with my Vietnamese badminton friend, Huy Lam Nguyen (Jones), about past exam papers of his stat course. I like the problem because it shows how indicator random variables can be used to count easily.