Maths Olympiad Prep

Library / /19 of 19

Combinatorics Difficulty 7.7 National Olympiad, round 2 Prove it Canada

Let AA, BB, 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, \dots, 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=(n1)A+BF = (n - 1)A + B, where nn is the positive integer such that
An+1BA<An. \frac{A}{n+1} \leq B - A < \frac{A}{n} .

Solution

Let B=A+CB = A + C where An+1C<An\frac{A}{n + 1} \leq C < \frac{A}{n}.

First, here is an informal sketch of the proof.

Lavaman's strategy: Use only safe intervals with nA+C1nA + C - 1 integers. The flea will start at position [1,C][1, C] from the left, which puts him at position [nA,nA+C1][nA, nA + C - 1] from the right. After n1n-1 jumps, he will still have nA(n1)(A+C)=A(n1)C>CnA - (n-1)(A+C) = A - (n-1)C > C distance to go, which is not enough for a big jump to clear the lava. Thus, he must do at least nn jumps in the safe interval, but that's possible only with all small jumps, and furthermore is impossible if the starting position is CC. This gives him starting position 1 higher in the next safe interval, so sooner or later the flea is going to hit the lava.

Flea's strategy: The flea just does one interval at a time. If the safe interval has at least nA+CnA + C integers in it, the flea has distance d>nAd > nA to go to the next lava when it starts. Repeatedly do big jumps until dd is between 11 and CmodAC \bmod A, then small jumps until the remaining distance is between 11 and CC, then a final big jump. This works as long as the first part does. However, we get at least nn big jumps since (d1)/A\lfloor(d-1)/A\rfloor can never go down two from a big jump (or we'd be done doing big jumps), so we get nn big jumps, and thus we are good if dmodAd \bmod A is in any of [1,C],[C+1,2C],,[nC+1,(n+1)C][1, C], [C+1, 2C], \dots, [nC+1, (n+1)C], but that's everything. \square

Let C=BAC = B - A. We shall write our intervals of lava in the form (Li,Ri]={Li+1,Li+2,,Ri}(L_i, R_i] = \{L_i + 1, L_i + 2, \dots, R_i\}, where Ri=Li+AR_i = L_i + A and Ri1<LiR_{i-1} < L_i for every i1i \geq 1. We also let R0=0R_0 = 0. We shall also represent a path for the flea as a sequence of integers x0,x1,x2,x_0, x_1, x_2, \dots where x0=0x_0 = 0 and xjxj1{A,B}x_j - x_{j-1} \in \{A, B\} for every j0j \geq 0.

Now here is a detailed proof.

First, assume F<(n1)A+B(=nA+C)F < (n-1)A + B (= nA + C): we must prove that Lavaman has a winning strategy. Let Li=Ri1+nA+C1L_i = R_{i-1} + nA + C - 1 for every i1i \geq 1. (Observe that nA+C1FnA + C - 1 \geq F.)

means that xj(Li,Ri]x_j \notin (L_i, R_i] for all i,j1i, j \geq 1. For each i1i \geq 1, let
Mi=max{xj:xjLi},mi=min{xj:xj>Ri}, andJ(i)=max{j:xjLi}. M_i = \max\{x_j : x_j \leq L_i\}, \quad m_i = \min\{x_j : x_j > R_i\}, \ \text{and} \quad J(i) = \max\{j : x_j \leq L_i\}.
Also let m0=0m_0 = 0. Then for i1i \geq 1 we have
Mi=xJ(i)andmi=xJ(i)+1. M_i = x_{J(i)} \quad \text{and} \quad m_i = x_{J(i)+1}.
Also, for every i1i \geq 1, we have
(a) mi=Mi+Bm_i = M_i + B (because Mi+ALi+A=RiM_i + A \leq L_i + A = R_i);
(b) LiMi>LiCL_i \geq M_i > L_i - C (since Mi=miB>RiB=Li+ABM_i = m_i - B > R_i - B = L_i + A - B);
(c) Ri<miRi+CR_i < m_i \leq R_i + C (since mi=Mi+BLi+B=Ri+Cm_i = M_i + B \leq L_i + B = R_i + C).

Mi+1=xJ(i+1)=xJ(i)+n+1xJ(i)+1+(n1)A+B>Ri+nA+C=Li+1+1>Mi+1 \begin{align*} M_{i+1} = x_{J(i+1)} = x_{J(i)+n+1} &\geq x_{J(i)+1} + (n-1)A + B \\ &> R_i + nA + C \\ &= L_{i+1} + 1 \\ &> M_{i+1} \end{align*}
which is a contradiction. This proves Claim 2.

xJ(i+1)+1=xJ(i)+n+2=xJ(i)+1+nA+B;i.e., mi+1=mi+nA+Bfor each i1. \begin{align*} x_{J(i+1)+1} &= x_{J(i)+n+2} = x_{J(i)+1} + nA + B; \\ \text{i.e., } m_{i+1} &= m_i + nA + B \quad \text{for each } i \geq 1. \end{align*}
Therefore
mi+1Ri+1=mi+nA+B(Ri+nA+C1+A)=miRi+1. \begin{align*} m_{i+1} - R_{i+1} &= m_i + nA + B - (R_i + nA + C - 1 + A) \\ &= m_i - R_i + 1. \end{align*}
Hence
CmC+1RC+1=m1R1+C>C C \geq m_{C+1} - R_{C+1} = m_1 - R_1 + C > C
which is a contradiction. Therefore no path for the flea avoids all the lava. We observe that Lavaman only needs to put lava on the first C+1C + 1 intervals.

Now assume F(n1)A+BF \geq (n-1)A + B. We will show that the flea can avoid all the lava. We shall need the following result:

Claim 3: Let dnAd \geq nA. Then there exist nonnegative integers ss and tt such that sA+tB(dC,d]sA + tB \in (d - C, d].

We shall prove this result at the end.

First, observe that L1nAL_1 \geq nA. By Claim 3, it is possible for the flea to make a sequence of jumps starting from 00 and ending at a point of (L1C,L1](L_1 - C, L_1]. From any point of this interval, a single jump of size BB takes the flea over (L1,R1](L_1, R_1] to a point in (R1,R1+C](R_1, R_1+C], which corresponds to the point xJ(1)+1(=m1)x_{J(1)+1} (= m_1) on the flea's path.

Now we use induction to prove that, for every i1i \geq 1, there is a path such that xjx_j avoids lava for all jJ(i)+1j \leq J(i)+1. The case i=1i=1 is done, so
assume that the assertion holds for a given ii. Then xJ(i)+1=mi(Ri,Ri+C]x_{J(i)+1} = m_i \in (R_i, R_i + C]. Therefore
Li+1miRi+F(Ri+C)=FCnA. L_{i+1} - m_i \geq R_i + F - (R_i + C) = F - C \geq nA.
Applying Claim 3 with d=Li+1mid = L_{i+1} - m_i shows that the flea can jump from mim_i to a point of (Li+1C,Li+1](L_{i+1} - C, L_{i+1}]. A single jump of size BB then takes the flea to a point of (Ri+1,Ri+1+C](R_{i+1}, R_{i+1} + C] (without visiting (Li+1,Ri+1](L_{i+1}, R_{i+1}]), and this point serves as xJ(i+1)+1x_{J(i+1)+1}. This completes the induction.

Proof of Claim 3: Let uu be the greatest integer that is less than or equal to d/Ad/A. Then unu \geq n and uAd<(u+1)AuA \leq d < (u+1)A. For v=0,,nv = 0, \dots, n, let
zv=(uv)A+vB=uA+vC. z_v = (u - v)A + vB = uA + vC.
Then
z0=uAd, z_0 = uA \leq d,
zn=uA+nC=uA+(n+1)CC(u+1)AC>dC. z_n = uA + nC = uA + (n + 1)C - C \geq (u + 1)A - C > d - C.
and zv+1zv=Cz_{v+1} - z_v = C for v=0,,n1v = 0, \dots, n-1.

Therefore we must have zv(dC,d]z_v \in (d-C, d] for some vv in {0,1,,n}\{0, 1, \dots, n\}. \square

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.