Problem

Source: 2016 CMO #4

Tags: combinatorics



Let $A, B$, and $F$ be positive integers, and assume $A < B < 2A$. A flea is at the number $0$ on the number line. The flea can move by jumping to the right by $A$ or by $B$. Before the flea starts jumping, Lavaman chooses finitely many intervals $\{m+1, m+2, \ldots, m+A\}$ consisting of $A$ consecutive positive integers, and places lava at all of the integers in the intervals. The intervals must be chosen so that: (i) any two distinct intervals are disjoint and not adjacent; (ii) there are at least $F$ positive integers with no lava between any two intervals; and (iii) no lava is placed at any integer less than $F$. Prove that the smallest $F$ for which the flea can jump over all the intervals and avoid all the lava, regardless of what Lavaman does, is $F = (n-1)A + B$, where $n$ is the positive integer such that $\frac{A}{n+1} \le B-A < \frac{A}{n}$.