Writeup: IMO Shortlist 2001 A1

19 Apr, 2025

Problem Statement:

Let $T$ denote the set of all ordered triples $(p, q, r)$ of nonnegative integers. Find all functions $f : T \to ℝ$ satisfying

f (p, q, r) = {\begin{matrix} 0 & if p q r = 0, \\ 1 + \frac{1}{6} (f (p + 1, q - 1, r) + f (p - 1, q + 1, r) \\ + f (p - 1, q, r + 1) + f (p + 1, q, r - 1) \\ + f (p, q + 1, r - 1) + f (p, q - 1, r + 1)) & otherwise \end{matrix}

for all nonnegative integers $p$ , $q$ , $r$ .

My Solution:

I've gotten asked a quant interview question almost exactly like this, so I'll rewrite the question in terms of that.

Consider the alternate (and equivalent) question: we have 3-player game involving players $A$ , $B$ , and $C$ , who have $p$ , $q$ , and $r$ coins respectively. Every second, one of $A$ , $B$ , and $C$ is randomly chosen, and they must give a coin to another randomly chosen player. What's the functions in terms of $p$ , $q$ , and $r$ will give the expected amount of time until one of $A$ , $B$ , or $C$ ruin?

We solve this problem with a martingale approach, with stopping condition $p$ , $q$ , or $r$ equal to $0$ . Let the amount of money players $A$ , $B$ , and $C$ have at timestep $i$ be $p_{i}$ , $q_{i}$ , and $r_{i}$ . Each of these sequences is a random walk. Consider the variable $S_{i} = p_{i} q_{i} r_{i}$ . We know that

𝔼 [S_{i + 1} | S_{i}] = S_{i} - \frac{p_{i} + q_{i} + r_{i}}{3}

which is apparent when substituing all equally likely values of $p_{i + 1}$ , $q_{i + 1}$ , and $r_{i + 1}$ into the expression for $S_{i + 1}$ . We also know that, at stopping time $n$ , $S_{n}$ must be $0$ .

We know that the quantity $p_{i} + q_{i} + r_{i}$ is conserved, let it be $S$ . Then the variable

M_{i} = S_{i} + i \cdot \frac{S}{3}

is a martingale, and $M_{0} = 0$ . So

𝔼 [M_{n}] = 𝔼 [M_{0}] = p_{0} q_{0} r_{0} = 𝔼 [S_{n} + n \cdot \frac{S}{3}] = \frac{S}{3} 𝔼 [n]

𝔼 [n] = \frac{3 p q r}{p + q + r} .

So $\frac{3 p q r}{p + q + r}$ is a candidate function for $f$ . Note that this must be the only function that works, since this expected value must be unique. So the only answer is $f = \frac{3 p q r}{p + q + r} .$