Maths Olympiad Prep

Library / /11 of 19

, 2021

Combinatorics Difficulty 5.2 AIME, harder Prove it United States

Problem:

Caroline starts with the number 11, and every second she flips a fair coin; if it lands heads, she adds 11 to her number, and if it lands tails she multiplies her number by 22. Compute the expected number of seconds it takes for her number to become a multiple of 20212021.

Solution

Solution:

Consider this as a Markov chain on Z/2021Z\mathbb{Z} / 2021 \mathbb{Z}. This Markov chain is aperiodic (since 00 can go to 00) and any number can be reached from any other number (by adding 11), so it has a unique stationary distribution π\pi, which is uniform (since the uniform distribution is stationary).

It is a well-known theorem on Markov chains that the expected return time from a state ii back to ii is equal to the inverse of the probability πi\pi_{i} of ii in the stationary distribution. (One way to see this is to take a length nn \rightarrow \infty random walk on this chain, and note that ii occurs roughly πi\pi_{i} of the time.) Since the probability of 00 is 12021\frac{1}{2021}, the expected return time from 00 to 00 is 20212021.

After the first step (from 00), we are at 11 with probability 1/21/2 and 00 with probability 1/21/2, so the number of turns it takes to get from 11 to 00 on expectation is 220212=40402 \cdot 2021 - 2 = 4040.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.