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}$.
Problem
Source: 2016 CMO #4
Tags: combinatorics
04.07.2016 14:31
Actually, just showing $ F=(n-1)A+B-1 $ doesn't work and $ F=(n-1)A+B $ works and both of it isn't hard P.S. Showing $ F=(n-1)A+B $ works is somewhat inductive? or something like that
16.11.2016 13:58
any idea
22.03.2017 03:49
From the conditions, A = A, and B = A + r where 0<r≤A-1. So n = $ \lceil \frac{A}{r} \rceil -1$, and F = $ \big( \lceil \frac{A}{r} \rceil -1 \big) \cdot A + \lfloor \frac{A}{r} \rfloor \cdot r + r$. You can figure out how many B's the flea needs to jump in each interval by finding the residue of the interval (between consecutive lava pits) length in mod A and finding the floor of the fraction with this residue on the numerator and r on the denominator. Once you jump this many B's, the rest can be allotted to A-length jumps. There's probably a more legit way to say this, but in worst case scenario, you need $\lceil \frac{A}{r} \rceil -1$ B's to get to a good position (where the flea can jump over a lava pit). This case results in F = $\big( \lceil \frac{A}{r} \rceil -1 \big) \cdot A + \lfloor \frac{A}{r} \rfloor \cdot r + r$. The extra r comes from the fact that you need to get within the zone (less than r away from the gap), not just outside of it. -This is by no means a proof, but just some thoughts that seem to work.
22.06.2020 06:46
Solution with jj_ca888. Let $C = B-A$. Let $u \to v$ denote the flea jumping from $u$ to $v$. Note that addition of an integer with an interval denotes elementwise addition, and the intervals used in this solution refer to integers only. We divide this solution into two parts. Part: 1 $F=nA+C$ is sufficient. Proof: We can divide the number line into safe and lava sections. Consider some safe section of length $nA + C + R$ where $0 \le R < A$. Redefine the number line so that $1$ is the beginning of this safe section. We will show that from any of the first $C$ positions or $[1, C]$, the flea can move to the first $C$ positions of the next safe section, or $(n + 1)A + C + R + [1, C]$. Clearly this is sufficient since if the safe section is at least $(n+1)A+C$ in length, we can simply jump by $A$ until we can apply this claim. Let $R = kC+r$ where $k$ and $r$ are nonnegative integers with $k$ maximal. Notice that $n + 1 > k$ since $\tfrac{R}{n+1} < \tfrac{A}{n+1} \le C$. Consider the following sequences of moves \[[r + 1, C] \stackrel{+(n-k)A \ +kB}{\to} nA + kC + [r + 1, C] = nA + R + [1, C-r].\]and \begin{align*} [1, r] \stackrel{+(n-k-1)A \ +(k+1)B}{\to} &nA + kC + [1, r] = nA + R + [1 + C-r, C] \quad \text{if } n \ge k + 1. \\ [1, r] \stackrel{+(n+1)A}{\to} &nA + A+ [1, r] = nA + R + [A-R+1, A-nC] \quad \text{if } n = k. \end{align*}Notice that these final ending positions lie in the interval $nA + R + [1, C]$ (the last one following from the fact that $\tfrac{A}{n+1} \le C$) which fits snugly into the safe section. Now taking another leap of length $B = A+C$ gives the desired. $\square$ Part 2: $F=nA+C$ is necessary Proof: Proceed similarly to Claim $1$; divide the number line into safe and lava sections. We claim that if lavaman simply makes every safe section of length $nA+C-1$, the flea cannot traverse $C$ lava intervals. In particular, we claim that if the flea is on some position in $[s, C]$ for some $s \le C$ where $1$ is defined as the first position of a particular safe section, then either it passes through $[s+1, C]$ where $1$ in this case is defined as the first position of the next safe section (basically taking reference frames here) or it can move no more. From now on $1$ is the first position of the former safe section. Now notice that our leap over the lava must be of length $B=A+C$, hence we must be in $[nA, nA+C-1]=nA+[0, C-1]$ for us to make this jump since the lava section ends at $(n+1)A + C - 1$. Say we move from somewhere in $[s, C]$ to somewhere in $nA+[0, C-1]$ in $n-1$ jumps. Then we need \[ (n-1)(A+C) \ge nA-C \iff A \le nC \iff B - A \ge \frac{A}{n},\]contradiction. Hence we need at least $n$ jumps. But $n$ jumps of length $A$ send $[s, C]$ to $nA + [s, C]$, so the flea must do exactly $n$ jumps of length $A$. Now $nA+C$ is lava, so if the flea was at $C$ in the beginning, it cannot make it past the lava. Otherwise, the flea is forced to do a jump of length $B=A+C$ and move to $nA + [s, C-1] + A+C = (n+1)A + C - 1 + [s + 1, C]$, as desired. Now the flea starts at position $1$ relative to its safe section which is inside $[1, C]$. Hence after $C$ lava intervals, the flea runs out of room. $\square$ Hence $F=nA+C = (n-1)A + B$ is minimal, as desired. $\blacksquare$