Maths Olympiad Prep

Library / /8 of 9

Combinatorics Difficulty 7.8 National Olympiad, round 2 Prove it Benelux Mathematical Olympiad

Problem:
Let n3n \geqslant 3 be an integer. A frog is to jump along the real axis, starting at the point 00 and making nn jumps: one of length 11, one of length 2,2, \ldots, one of length nn. It may perform these nn jumps in any order. If at some point the frog is sitting on a number a0a \leqslant 0, its next jump must be to the right (towards the positive numbers). If at some point the frog is sitting on a number a>0a>0, its next jump must be to the left (towards the negative numbers). Find the largest positive integer kk for which the frog can perform its jumps in such an order that it never lands on any of the numbers 1,2,,k1,2, \ldots, k.

Solution

Solution:
We claim that the largest positive integer kk with the given property is n12\left\lfloor\frac{n-1}{2}\right\rfloor, where x\lfloor x\rfloor is by definition the largest integer not exceeding xx.

Consider a sequence of nn jumps of length 1,2,,n1,2, \ldots, n such that the frog never lands on any of the numbers 1,2,,k1,2, \ldots, k, where k1k \geqslant 1. Note that we must have k<nk<n in order for the frog to be able to make its first jump. As the frog jumps to the right only if it is in a number a0a \leqslant 0, and the largest jump has length nn, it is impossible to reach numbers greater than nn. On the other hand, suppose the frog is in a number a>0a>0, then it must even be in a number ak+1a \geqslant k+1, since it is not allowed to hit the numbers 1,2,,k1,2, \ldots, k. So the frog jumps to the left only if it is in a number ak+1a \geqslant k+1, and therefore it is impossible to reach numbers less than (k+1)n=kn+1(k+1)-n = k-n+1. This means the frog only possibly lands on the numbers ii satisfying
kn+1i0ork+1in. k-n+1 \leqslant i \leqslant 0 \quad \text{or} \quad k+1 \leqslant i \leqslant n.
When performing a jump of length kk, the frog has to remain at either side of the numbers 1,2,,k1,2, \ldots, k. Indeed, jumping over 1,2,,k1,2, \ldots, k requires a jump of at least length k+1k+1. In case it starts at a number a>0a>0 (in fact k+1ank+1 \leqslant a \leqslant n), it lands in aka-k and we must also have akk+1a-k \geqslant k+1. So 2k+1an2k+1 \leqslant a \leqslant n, therefore 2k+1n2k+1 \leqslant n. In case it starts at a number a0a \leqslant 0 (in fact kn+1a0k-n+1 \leqslant a \leqslant 0), it lands in a+ka+k and we must also have a+k0a+k \leqslant 0. Adding kk to both sides of kn+1ak-n+1 \leqslant a, we obtain 2kn+1a+k02k-n+1 \leqslant a+k \leqslant 0, so in this case we have 2k+1n2k+1 \leqslant n as well. We conclude that kn12k \leqslant \frac{n-1}{2}. Since kk is integer, we even have kn12k \leqslant \left\lfloor\frac{n-1}{2}\right\rfloor.

Next we prove that this upper bound is sharp: for k=n12k=\left\lfloor\frac{n-1}{2}\right\rfloor the frog really can perform its jumps in such an order that it never lands on any of the numbers 1,2,,k1,2, \ldots, k.

Suppose nn is odd, then n12\frac{n-1}{2} is an integer and we have k=n12k=\frac{n-1}{2}, so n=2k+1n=2k+1. We claim that when the frog performs the jumps of length 1,,2k+11, \ldots, 2k+1 in the following order, it does never land on 1,2,,k1,2, \ldots, k: it starts with a jump of length k+1k+1, then it performs two jumps, one of length k+2k+2 followed by one of length 11, next two jumps of length k+3k+3 and 22, \ldots, next two jumps of length k+(i+1)k+(i+1) and ii, \ldots, and finally two jumps of length k+(k+1)k+(k+1) and kk. In this order of the jumps every length between 11 and n=2k+1n=2k+1 does occur: it performs a pair of jumps for 1ik1 \leqslant i \leqslant k, which are the jumps of length 1,2,,k1,2, \ldots, k and the jumps of length k+2,k+3,,2k+1k+2, k+3, \ldots, 2k+1, and it starts with the jump of length k+1k+1.

We now prove the correctness of this jumping scheme. After the first jump the frog lands in k+1>kk+1>k. Now suppose the frog is in 00 or k+1k+1 and is about to perform the pair of jumps of length k+(i+1)k+(i+1) and ii. Starting from 00, it lands in k+(i+1)>kk+(i+1)>k, after which it lands in (k+i+1)i=k+1>k(k+i+1)-i=k+1>k. If on the contrary it starts in k+1k+1, it lands in (k+1)(k+(i+1))=i<1(k+1)-(k+(i+1))=-i<1, after which it lands in (i)+i=0(-i)+i=0. We see that, starting in 00, the frog lands in k+1k+1 after the pair of jumps, while starting in k+1k+1 the frog lands in 00, while in both cases the jumps do not touch 1,2,,k1,2, \ldots, k. This proves the correctness of its series of jumps. As the frog (after its first jump) alternates between k+1k+1 and 00 exactly kk times, for odd kk it will end up in 00, while for even kk it will end up in k+1k+1.

Suppose nn is even, then n12\frac{n-1}{2} is not an integer and we have k=n1212=n22k=\frac{n-1}{2}-\frac{1}{2}=\frac{n-2}{2}, so n=2k+2n=2k+2. Let the frog firstly perform the same series of jumps as in the previous case; they still do not touch 1,2,,k1,2, \ldots, k. Now let the frog make a final extra jump of length 2k+22k+2. It will land in 0+(2k+2)=2k+2>k0+(2k+2)=2k+2>k if kk is odd, or in (k+1)(2k+2)=k1<1(k+1)-(2k+2)=-k-1<1 if kk is even, and its series of jumps is correct again.

We conclude that the largest positive integer kk with the given property is n12\left\lfloor\frac{n-1}{2}\right\rfloor.

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.