Difference between revisions of "2019 IMO Problems/Problem 5"

Latest revision as of 00:51, 19 November 2023

Problem

The Bank of Bath issues coins with an $H$ on one side and a $T$ on the other. Harry has $n$ of these coins arranged in a line from left to right. He repeatedly performs the following operation:

If there are exactly $k > 0$ coins showing $H$ , then he turns over the $k^{th}$ coin from the left; otherwise, all coins show $T$ and he stops. For example, if $n = 3$ the process starting with the configuration $THT$ would be $THT \rightarrow HHT \rightarrow HTT \rightarrow TTT$ , which stops after three operations.

(a) Show that, for each initial configuration, Harry stops after a finite number of operations.

(b) For each initial configuration $C$ , let $L(C)$ be the number of operations before Harry stops. For example, $L(THT) = 3$ and $L(TTT) = 0$ . Determine the average value of $L(C)$ over all $2^n$ possible initial configurations $C$ .

Solution

Solution 1 (Induction and Case Division)

Don't worry, this is way simpler than it's length may suggest :)

Claim: The expected value of $L(C)$ is $\frac{n(n+1)}{4}$ .

We prove parts A and B simultaneously using induction.

Base case: $n=1$

$L(T)=0$ and $L(H)=1$ , and these are the only possibilities, so clearly the process terminates and $E[L(C)] = \frac{1}{2} = \frac{1*2}{4}$ .

Inductive step: Assume that for $n-1$ coins, the process always terminates, and $E[L(C)] = \frac{n(n-1)}{4}$ . Define $E_{n-1} = E[L(C)]$ here. Now, for $n$ coins, define $E_{n} = E[L{C}]$ across all $2^n$ configurations. Consider cases on the last coin:

Case 1: Final coin is $T$

If the last coin is $T$ , then we simply can forget about it, as we can flip it to heads only if we have n heads, which is impossible. This occurs with probablity $P_{T} = 1/2$ , and will be identical to the general $n-1$ case; thus, this process terminates, and we will have an expected number of moves here of $E_{n-1}$ .

Case 2: Final coin is $H$

The probability that this occurs is $P_{H} = 1/2$ . The only way we have for the process to terminate now is for all coins to show heads, after which we can progressively flip each coin from right to left (this will take $n$ moves). Thus, we now have a new goal for the first $n-1$ coins (given the head at the end); get all heads.

We claim that this process is symmetrical to the original process on $n-1$ coins, and thus it terminates and has the expected number of moves $E_{n-1}$ .

Proof: Let us have $k \ge 1$ heads in our group of n coins, of which $k-1$ are in the first n-1. We are supposed to flip the $k$ 'th coin from the left in the first n-1 coins, which is equivalent to flipping the $(n-k)$ 'th coin from the right (in the first $n-1$ coins, NOT all $n$ coins), but there are $n-k$ tails in the first $n-1$ coins! We now have a new process defined as follows:

Consider a configuration of $n-1$ coins with $x \ge 1$ tails, and flip the x'th coin from the right, and keep flipping until all coins are heads.

This is clearly symmetric to the original process, and will terminate if and only if the original process on $n-1$ coins does, and has the same expected number of moves as the original. Thus, the claim is proven.

Back to the case: We now have a process to get to all heads that will terminate with an expected number of steps of $E_{n-1}$ , and then an n-step algorithm to reach the finish. Thus, here also, the process terminates, and we have a total expected number of steps as $E_{n-1}+n$ .

Thus, the overall process on n coins will terminate, since the process terminates in both the representative cases on n-1 coins. $\boxed{Q.E.D}$ Also, the expected value of steps can be easily computed now; $E_{n} = (P_{T})(E_{n-1})+(P_{H})(E_{n-1}+n) = E_{n-1}+n/2 = \frac{n(n-1}{4}+\frac{n}{2} = \boxed{\frac{n(n+1)}{4}}$ as desired. We are now done.

-Solution by thanosaops

Solution 2 (Strong Induction and Alternative Case Division)

We define a sequence $\{a_i\}_{i=1}^n$ : $a_i=1$ if the $i$ 'th coin is $H$ and $a_i=0$ if the $i$ 'th coin is $T$ . Then, $k$ will be the number of $1$ 's in $\{a_i\}$ and after each operation, $a_k$ will be changed to $1-a_k$ . Let $f(n)=\sum L\{a_i\}=$ sum of $L\{a_i\}$ over all possible $\{a_i\}$ (of length $n$ ).

We shall prove that the process terminates and find the value of $f(n)$ using strong induction.

Base case: Clearly, for $n=1$ , the process terminates.

Induction hypothesis: For $n=1, 2, 3, \cdots, k$ , the process terminates.

Inductive step: We claim that for $n=k+1$ , the process terminates as well.

Case 1: $a_1=1$

This means that $\{a_i\}=\{1, a_2, a_3, \cdots, a_n\}$ . With the proof of the claim in Solution 1, we can similarly prove that operating on $\{a_i\}$ is equivalent to operating on $\{a_2, a_3, \cdots, a_n\}$ .

By our induction hypothesis, this process will terminate, and hence $\{a_i\}$ will be changed to $\{1, 0, 0, \cdots, 0\}$ at the end of this process. Now, we operate one more time to change $a_1$ from $1$ to $0$ . Hence, the process terminates.

We can also see that $L\{a_i\}=L\{a_2, a_3, \cdots, a_n\}+1$ . Hence, sum of $L\{a_i\}$ over all possible $\{a_i\}$ in this case $=\sum L\{a_i\}=\sum \left[L\{a_2, a_3, \cdots, a_n\}+1\right]=f(n-1)+2^{n-1}$

Case 2: $a_1=0$ and $a_n=1$

This means that $\{a_i\}=\{0, a_2, a_3, \cdots, a_{n-1}, 1\}$ . Operating on $\{a_i\}$ is now equivalent to operating on $\{a_2, a_3, \cdots, a_{n-1}\}$ .

By our induction hypothesis, this process will terminate, and hence $\{a_i\}$ will be changed to $\{0, 0, 0, \cdots, 0, 1\}$ at the end of this process. Now, since $k=1$ , $a_1$ will become $1$ . Now, $k=2$ , so $a_2$ will become $1$ as well. This process will repeat until $k=n$ and $\{a_i\}$ has been changed to $\{1, 1, 1, \cdots, 1\}$ . Now, since $k=n$ , $a_n$ will become $0$ . Now, $k=n-1$ , so $a_{n-1}$ will become $0$ as well. This process will repeat again until $k=0$ and $\{a_i\}$ has been changed to $\{0, 0, 0, \cdots, 0\}$ . Hence, the process terminates.

We can also see that $L\{a_i\}=L\{a_2, a_3, \cdots, a_{n-1}\}+(2n-1)$ . Hence, sum of $L\{a_i\}$ over all possible $\{a_i\}$ in this case $=\sum L\{a_i\}=\sum \left[L\{a_2, a_3, \cdots, a_{n-1}\}+(2n-1)\right]=f(n-2)+2^{n-2}\cdot(2n-1)$

Case 3: $a_n=0$

This means that $\{a_i\}=\{a_1, a_2, a_3, \cdots, a_{n-1}, 0\}$ . Operating on $\{a_i\}$ is now equivalent to operating on $\{a_1, a_2, \cdots, a_{n-1}\}$ .

By our induction hypothesis, this process will terminate, and hence $\{a_i\}$ will be changed to $\{0, 0, 0, \cdots, 0, 0\}$ at the end of this process. Hence, the process terminates.

We can also see that $L\{a_i\}=L\{a_1, a_2, \cdots, a_{n-1}\}$ . Hence, sum of $L\{a_i\}$ over all possible $\{a_i\}$ in this case $=\sum L\{a_i\}=\sum \left[L\{a_1, a_2, \cdots, a_{n-1}\}\right]=f(n-1)$

This is already sufficient to prove part A, but we want to find $f(n)$ too, and we have overcounted!

Case 4: $a_1=1$ and $a_n=0$ (This is what we have overcounted)

This means that $\{a_i\}=\{1, a_2, a_3, \cdots, a_{n-1}, 0\}$ . Operating on $\{a_i\}$ is now equivalent to operating on $\{a_2, a_3, \cdots, a_{n-1}\}$ .

By our induction hypothesis, this process will terminate, and hence $\{a_i\}$ will be changed to $\{1, 0, 0, \cdots, 0, 0\}$ at the end of this process. Now, we operate one more time to change $a_1$ from $1$ to $0$ . Hence, the process terminates.

We can also see that $L\{a_i\}=L\{a_2, a_3, \cdots, a_{n-1}\}+1$ . Hence, sum of $L\{a_i\}$ over all possible $\{a_i\}$ in this case $=\sum L\{a_i\}=\sum \left[L\{a_1, a_2, \cdots, a_{n-1}\}+1\right]=f(n-2)+2^{n-2}$

Hence, we have proven that for all configurations, the process terminates, $\boxed{Q.E.D.}$ Now, all that remains is to calculate $f(n)$ .

$\begin{align*} f(n) &= f(n-1)+2^{n-1}+f(n-2)+2^{n-2}\cdot(2n-1)+f(n-1)-\left[f(n-2)+2^{n-2}\right] \\ &= 2f(n-1)+2^{n-1}\cdot n \end{align*}$

This can be rearranged to give us

$f(n)-n(n+1)\cdot2^{n-2}=2\left[f(n-1)-n(n-1)\cdot2^{n-3}\right]$

When $n=1$ , $f(n)-n(n+1)\cdot2^{n-2}=0$ . This is good, because now we know that $\forall n\in\mathbb{Z}^{+}, f(n)-n(n+1)\cdot2^{n-2}=0$ i.e. $f(n)=n(n+1)\cdot2^{n-2}$ .

Now the average will be $\frac{n(n+1)\cdot2^{n-2}}{2^n}=\boxed{\frac{1}{4}n(n+1)}$

~IraeVid13

@@ Line 12: / Line 12: @@
 ==Solution==
+===Solution 1 (Induction and Case Division)===
 Don't worry, this is way simpler than it's length may suggest :)
@@ Line 23: / Line 25: @@
 <math>L(T)=0</math> and <math>L(H)=1</math>, and these are the only possibilities, so clearly the process terminates and <math>E[L(C)] = \frac{1}{2} = \frac{1*2}{4}</math>.
-Inductive step: Assume that for <math>n-1</math> coins, the process always terminates, and <math>E[L(C)] = \frac{n(n-1)}{4}</math>. Define <math>E_{n-1} = E[L(C)]</math> here. Now, for n coins, define <math>E_{n} = E[L{C}]</math> across all <math>2^n</math> configurations. Consider cases on the last coin:
+Inductive step: Assume that for <math>n-1</math> coins, the process always terminates, and <math>E[L(C)] = \frac{n(n-1)}{4}</math>. Define <math>E_{n-1} = E[L(C)]</math> here. Now, for <math>n</math> coins, define <math>E_{n} = E[L{C}]</math> across all <math>2^n</math> configurations. Consider cases on the last coin:
 Case 1: Final coin is <math>T</math>
-If the last coin is T, then we simply can forget about it, as we can flip it to heads only if we have n heads, which is impossible. This occurs with probablity <math>P_{T} = 1/2</math>, and will be identical to the general n-1 case; thus, this process terminates, and we will have an expected number of moves here of <math>E_{n-1}</math>.
+If the last coin is <math>T</math>, then we simply can forget about it, as we can flip it to heads only if we have n heads, which is impossible. This occurs with probablity <math>P_{T} = 1/2</math>, and will be identical to the general <math>n-1</math> case; thus, this process terminates, and we will have an expected number of moves here of <math>E_{n-1}</math>.
 Case 2: Final coin is <math>H</math>
-The probability that this occurs is <math>P_{H} = 1/2</math>. The only way we have for the process to terminate now is for all coins to show heads, after which we can progressively flip each coin from right to left (this will take n moves). Thus, we now have a new goal for the first n-1 coins (given the head at the end); get all heads.
+The probability that this occurs is <math>P_{H} = 1/2</math>. The only way we have for the process to terminate now is for all coins to show heads, after which we can progressively flip each coin from right to left (this will take <math>n</math> moves). Thus, we now have a new goal for the first <math>n-1</math> coins (given the head at the end); get all heads.
- We claim that this process is symmetrical to the original process on n-1 coins, and thus it terminates and has the expected number of moves <math>E_{n-1}</math>.
+We claim that this process is symmetrical to the original process on <math>n-1</math> coins, and thus it terminates and has the expected number of moves <math>E_{n-1}</math>.
-Proof: Let us have <math>k \ge 1</math> heads in our group of n coins, of which <math>k-1</math> are in the first n-1. We are supposed to flip the k'th coin from the left in the first n-1 coins, which is equivalent to flipping the (n-k)'th coin from the right (in the first n-1 coins, NOT all n coins), but there are n-k tails in the first n-1 coins! We now have a new process defined as follows:
+Proof: Let us have <math>k \ge 1</math> heads in our group of n coins, of which <math>k-1</math> are in the first n-1. We are supposed to flip the <math>k</math>'th coin from the left in the first n-1 coins, which is equivalent to flipping the <math>(n-k)</math>'th coin from the right (in the first <math>n-1</math> coins, NOT all <math>n</math> coins), but there are <math>n-k</math> tails in the first <math>n-1</math> coins! We now have a new process defined as follows:
-Consider a configuration of n-1 coins with <math>x \ge 1</math> tails, and flip the x'th coin from the right, and keep flipping until all coins are heads.
+Consider a configuration of <math>n-1</math> coins with <math>x \ge 1</math> tails, and flip the x'th coin from the right, and keep flipping until all coins are heads.
-This is clearly symmetric to the original process, and will terminate if and only if the original process on n-1 coins does, and has the same expected number of moves as the original. Thus, the claim is proven.
+This is clearly symmetric to the original process, and will terminate if and only if the original process on <math>n-1</math> coins does, and has the same expected number of moves as the original. Thus, the claim is proven.
 Back to the case: We now have a process to get to all heads that will terminate with an expected number of steps of <math>E_{n-1}</math>, and then an n-step algorithm to reach the finish. Thus, here also, the process terminates, and we have a total expected number of steps as <math>E_{n-1}+n</math>.
-Thus, the overall process on n coins will terminate, since the process terminates in both the representative cases on n-1 coins. Also, the expected value of steps can be easily computed now; <math>E_{n} = (P_{T})(E_{n-1})+(P_{H})(E_{n-1}+n) = E_{n-1}+n/2 = \frac{n(n-1}{4}+\frac{n}{2} = \frac{n(n+1)}{4}</math> as desired. We are now done. Q.E.D.
+Thus, the overall process on n coins will terminate, since the process terminates in both the representative cases on n-1 coins. <math>\boxed{Q.E.D}</math> Also, the expected value of steps can be easily computed now; <math>E_{n} = (P_{T})(E_{n-1})+(P_{H})(E_{n-1}+n) = E_{n-1}+n/2 = \frac{n(n-1}{4}+\frac{n}{2} = \boxed{\frac{n(n+1)}{4}}</math> as desired. We are now done.
 -Solution by thanosaops
+=== Solution 2 (Strong Induction and Alternative Case Division) ===
+We define a sequence <math>\{a_i\}_{i=1}^n</math>: <math>a_i=1</math> if the <math>i</math>'th coin is <math>H</math> and <math>a_i=0</math> if the <math>i</math>'th coin is <math>T</math>. Then, <math>k</math> will be the number of <math>1</math>'s in <math>\{a_i\}</math> and after each operation, <math>a_k</math> will be changed to <math>1-a_k</math>. Let <math>f(n)=\sum L\{a_i\}=</math> sum of <math>L\{a_i\}</math> over all possible <math>\{a_i\}</math> (of length <math>n</math>).
+We shall prove that the process terminates and find the value of <math>f(n)</math> using strong induction.
+Base case: Clearly, for <math>n=1</math>, the process terminates.
+Induction hypothesis: For <math>n=1, 2, 3, \cdots, k</math>, the process terminates.
+Inductive step: We claim that for <math>n=k+1</math>, the process terminates as well.
+Case 1: <math>a_1=1</math>
+This means that <math>\{a_i\}=\{1, a_2, a_3, \cdots, a_n\}</math>. With the proof of the claim in Solution 1, we can similarly prove that operating on <math>\{a_i\}</math> is equivalent to operating on <math>\{a_2, a_3, \cdots, a_n\}</math>.
+By our induction hypothesis, this process will terminate, and hence <math>\{a_i\}</math> will be changed to <math>\{1, 0, 0, \cdots, 0\}</math> at the end of this process. Now, we operate one more time to change <math>a_1</math> from <math>1</math> to <math>0</math>. Hence, the process terminates.
+We can also see that <math>L\{a_i\}=L\{a_2, a_3, \cdots, a_n\}+1</math>. Hence, sum of <math>L\{a_i\}</math> over all possible <math>\{a_i\}</math> in this case <cmath>=\sum L\{a_i\}=\sum \left[L\{a_2, a_3, \cdots, a_n\}+1\right]=f(n-1)+2^{n-1}</cmath>
+Case 2: <math>a_1=0</math> and <math>a_n=1</math>
+This means that <math>\{a_i\}=\{0, a_2, a_3, \cdots, a_{n-1}, 1\}</math>. Operating on <math>\{a_i\}</math> is now equivalent to operating on <math>\{a_2, a_3, \cdots, a_{n-1}\}</math>.
+By our induction hypothesis, this process will terminate, and hence <math>\{a_i\}</math> will be changed to <math>\{0, 0, 0, \cdots, 0, 1\}</math> at the end of this process. Now, since <math>k=1</math>, <math>a_1</math> will become <math>1</math>. Now, <math>k=2</math>, so <math>a_2</math> will become <math>1</math> as well. This process will repeat until <math>k=n</math> and <math>\{a_i\}</math> has been changed to <math>\{1, 1, 1, \cdots, 1\}</math>. Now, since <math>k=n</math>, <math>a_n</math> will become <math>0</math>. Now, <math>k=n-1</math>, so <math>a_{n-1}</math> will become <math>0</math> as well. This process will repeat again until <math>k=0</math> and <math>\{a_i\}</math> has been changed to <math>\{0, 0, 0, \cdots, 0\}</math>. Hence, the process terminates.
+We can also see that <math>L\{a_i\}=L\{a_2, a_3, \cdots, a_{n-1}\}+(2n-1)</math>. Hence, sum of <math>L\{a_i\}</math> over all possible <math>\{a_i\}</math> in this case <cmath>=\sum L\{a_i\}=\sum \left[L\{a_2, a_3, \cdots, a_{n-1}\}+(2n-1)\right]=f(n-2)+2^{n-2}\cdot(2n-1)</cmath>
+Case 3: <math>a_n=0</math>
+This means that <math>\{a_i\}=\{a_1, a_2, a_3, \cdots, a_{n-1}, 0\}</math>. Operating on <math>\{a_i\}</math> is now equivalent to operating on <math>\{a_1, a_2, \cdots, a_{n-1}\}</math>.
+By our induction hypothesis, this process will terminate, and hence <math>\{a_i\}</math> will be changed to <math>\{0, 0, 0, \cdots, 0, 0\}</math> at the end of this process. Hence, the process terminates.
+We can also see that <math>L\{a_i\}=L\{a_1, a_2, \cdots, a_{n-1}\}</math>. Hence, sum of <math>L\{a_i\}</math> over all possible <math>\{a_i\}</math> in this case <cmath>=\sum L\{a_i\}=\sum \left[L\{a_1, a_2, \cdots, a_{n-1}\}\right]=f(n-1)</cmath>
+This is already sufficient to prove part A, but we want to find <math>f(n)</math> too, and we have overcounted!
+Case 4: <math>a_1=1</math> and <math>a_n=0</math> (This is what we have overcounted)
+This means that <math>\{a_i\}=\{1, a_2, a_3, \cdots, a_{n-1}, 0\}</math>. Operating on <math>\{a_i\}</math> is now equivalent to operating on <math>\{a_2, a_3, \cdots, a_{n-1}\}</math>.
+By our induction hypothesis, this process will terminate, and hence <math>\{a_i\}</math> will be changed to <math>\{1, 0, 0, \cdots, 0, 0\}</math> at the end of this process. Now, we operate one more time to change <math>a_1</math> from <math>1</math> to <math>0</math>. Hence, the process terminates.
+We can also see that <math>L\{a_i\}=L\{a_2, a_3, \cdots, a_{n-1}\}+1</math>. Hence, sum of <math>L\{a_i\}</math> over all possible <math>\{a_i\}</math> in this case <cmath>=\sum L\{a_i\}=\sum \left[L\{a_1, a_2, \cdots, a_{n-1}\}+1\right]=f(n-2)+2^{n-2}</cmath>
+Hence, we have proven that for all configurations, the process terminates, <math>\boxed{Q.E.D.}</math> Now, all that remains is to calculate <math>f(n)</math>.
+<cmath>\begin{align*}
+f(n) &= f(n-1)+2^{n-1}+f(n-2)+2^{n-2}\cdot(2n-1)+f(n-1)-\left[f(n-2)+2^{n-2}\right] \\
+&= 2f(n-1)+2^{n-1}\cdot n
+\end{align*}</cmath>
+This can be rearranged to give us
+<cmath>f(n)-n(n+1)\cdot2^{n-2}=2\left[f(n-1)-n(n-1)\cdot2^{n-3}\right]</cmath>
+When <math>n=1</math>, <math>f(n)-n(n+1)\cdot2^{n-2}=0</math>. This is good, because now we know that <math>\forall n\in\mathbb{Z}^{+}, f(n)-n(n+1)\cdot2^{n-2}=0</math> i.e. <math>f(n)=n(n+1)\cdot2^{n-2}</math>.
+Now the average will be <math>\frac{n(n+1)\cdot2^{n-2}}{2^n}=\boxed{\frac{1}{4}n(n+1)}</math>
+~[[User:Iraevid13|IraeVid13]]
+==See Also==
+{{IMO box|year=2019|num-b=4|num-a=6}}

2019 IMO (Problems) • Resources
Preceded by Problem 4	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 6
All IMO Problems and Solutions

Page

Toolbox

Search