2025 SSMO Team Round Problems/Problem 8

Problem

Adam has a fair coin with a $2$ written on one side and a $3$ written on the other. What is the expected number of times Adam needs to flip the coin for the sum of all his coin flips to be a multiple of $36$ ?

Solution

We proceed via states. Suppose after some number of coin flips (possibly zero), the remainder when the sum of Adam's coin flips is divided by $36$ is $t$ . Then, let $e_t$ denote the expected number of flips Adam needs for the sum of all his flips to be a multiple of $36$ if he must flip his coin at least once, and let $e'_t$ denote the expected number of flips Adam needs for the sum of all his flips to be a multiple of $36$ if he does not necessarily have to flip his coin at least once. We seek the value of $e_0$ .

For every integer $0\le t \le 35$ , we have $e_t = \tfrac{1}{2}e'_{t+2} + \tfrac{1}{2}e'_{t+3} + 1$ , where we consider subscrips modulo $36$ . Consider the equation obtained by adding all $36$ equations of this form together. The left hand side is simply $e_0+e_1+\cdots e_{35}$ . Since $t\to t+2$ and $t\to t+3$ are both bijections modulo $36$ , the right hand side is $\tfrac{1}{2}(e'_0+e'_1+\cdots+e'_{35}) + \tfrac{1}{2}(e'_0+e'_1+\cdots+e'_{35}) + 36$ . Therefore, we have $\sum_{i=0}^{35} e_i = \sum_{i=0}^{35}e'_i + 36.$ Now, it is obviously impossible for the sum of Adam's coin flips to be a multiple of $36$ zero flips after his sum is not a multiple of $36$ . Thus, for all valid $t\ne 0$ , we have $e'_t = e_t$ . Hence, our $72$ -variable equation above simplifies neatly as $e_0 = e'_0 + 36$ . Trivially, $e'_0 = 0$ , so $e_0 = \boxed{36}$ .

~Sedro

Page

Toolbox

Search

2025 SSMO Team Round Problems/Problem 8

Problem

Solution