Library / /731 of 740

, 2019

Combinatorics Difficulty 5.9 AIME, harder Prove it United States

Problem:

Let $p$ be a real number between $0$ and $1$ . Jocelin has a coin that lands heads with probability $p$ and tails with probability $1-p$ ; she also has a number written on a blackboard. Each minute, she flips the coin, and if it lands heads, she replaces the number $x$ on the blackboard with $3x+1$ ; if it lands tails she replaces it with $x/2$ . Given that there are constants $a, b$ such that the expected value of the value written on the blackboard after $t$ minutes can be written as $at+b$ for all positive integers $t$ , compute $p$ .

Solution

Solution:

If the blackboard has the value $x$ written on it, then the expected value of the value after one flip is
$f(x) = p(3x + 1) + (1-p) \frac{x}{2}$
Because this expression is linear, we can say the same even if we only know the blackboard's initial expected value is $x$ . Therefore, if the blackboard value is $x_0$ at time $0$ , then after $t$ minutes, the expected blackboard value is $f^{t}(x_0)$ . We are given that $x_0, f(x_0), f^{2}(x_0), \ldots$ is an arithmetic sequence, so for there to be a constant difference, we must have $f(x) = x + c$ for some $c$ .
This only occurs when $3p + (1-p)/2 = 1$ , so $p = 1/5$ .

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.