MathDB

4

Part of 2016 Canada National Olympiad

Problems(1)

Lavaman versus the Flea

Source: 2016 CMO #4

4/10/2016
Let A,BA, B, and FF be positive integers, and assume A<B<2AA < B < 2A. A flea is at the number 00 on the number line. The flea can move by jumping to the right by AA or by BB. Before the flea starts jumping, Lavaman chooses finitely many intervals {m+1,m+2,…,m+A}\{m+1, m+2, \ldots, m+A\} consisting of AA 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 FF positive integers with no lava between any two intervals; and (iii) no lava is placed at any integer less than FF.
Prove that the smallest FF 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+BF = (n-1)A + B, where nn is the positive integer such that An+1≤B−A<An\frac{A}{n+1} \le B-A < \frac{A}{n}.
combinatorics