2019 IMO Problems/Problem 5
Contents
[hide]Problem
The Bank of Bath issues coins with an on one side and a on the other. Harry has of these coins arranged in a line from left to right. He repeatedly performs the following operation:
If there are exactly coins showing , then he turns over the coin from the left; otherwise, all coins show and he stops. For example, if the process starting with the configuration would be , 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 , let be the number of operations before Harry stops. For example, and . Determine the average value of over all possible initial configurations .
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 is .
We prove parts A and B simultaneously using induction.
Base case:
and , and these are the only possibilities, so clearly the process terminates and .
Inductive step: Assume that for coins, the process always terminates, and . Define here. Now, for coins, define across all configurations. Consider cases on the last coin:
Case 1: Final coin is
If the last coin is , 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 , and will be identical to the general case; thus, this process terminates, and we will have an expected number of moves here of .
Case 2: Final coin is
The probability that this occurs is . 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 moves). Thus, we now have a new goal for the first coins (given the head at the end); get all heads.
We claim that this process is symmetrical to the original process on coins, and thus it terminates and has the expected number of moves .
Proof: Let us have heads in our group of n coins, of which are in the first n-1. We are supposed to flip the 'th coin from the left in the first n-1 coins, which is equivalent to flipping the 'th coin from the right (in the first coins, NOT all coins), but there are tails in the first coins! We now have a new process defined as follows:
Consider a configuration of coins with 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 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 , 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 .
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; as desired. We are now done.
-Solution by thanosaops
Solution 2 (Strong Induction and Alternative Case Division)
We define a sequence : if the 'th coin is and if the 'th coin is . Then, will be the number of 's in and after each operation, will be changed to . Let sum of over all possible (of length ).
We shall prove that the process terminates and find the value of using strong induction.
Base case: Clearly, for , the process terminates.
Induction hypothesis: For , the process terminates.
Inductive step: We claim that for , the process terminates as well.
Case 1:
This means that . With the proof of the claim in Solution 1, we can similarly prove that operating on is equivalent to operating on .
By our induction hypothesis, this process will terminate, and hence will be changed to at the end of this process. Now, we operate one more time to change from to . Hence, the process terminates.
We can also see that . Hence, sum of over all possible in this case
Case 2: and
This means that . Operating on is now equivalent to operating on .
By our induction hypothesis, this process will terminate, and hence will be changed to at the end of this process. Now, since , will become . Now, , so will become as well. This process will repeat until and has been changed to . Now, since , will become . Now, , so will become as well. This process will repeat again until and has been changed to . Hence, the process terminates.
We can also see that . Hence, sum of over all possible in this case
Case 3:
This means that . Operating on is now equivalent to operating on .
By our induction hypothesis, this process will terminate, and hence will be changed to at the end of this process. Hence, the process terminates.
We can also see that . Hence, sum of over all possible in this case
This is already sufficient to prove part A, but we want to find too, and we have overcounted!
Case 4: and (This is what we have overcounted)
This means that . Operating on is now equivalent to operating on .
By our induction hypothesis, this process will terminate, and hence will be changed to at the end of this process. Now, we operate one more time to change from to . Hence, the process terminates.
We can also see that . Hence, sum of over all possible in this case
Hence, we have proven that for all configurations, the process terminates, Now, all that remains is to calculate .
This can be rearranged to give us
When , . This is good, because now we know that i.e. .
Now the average will be
See Also
2019 IMO (Problems) • Resources | ||
Preceded by Problem 4 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 6 |
All IMO Problems and Solutions |