Problem:
Let be an integer. A frog is to jump along the real axis, starting at the point and making jumps: one of length , one of length , one of length . It may perform these jumps in any order. If at some point the frog is sitting on a number , its next jump must be to the right (towards the positive numbers). If at some point the frog is sitting on a number , its next jump must be to the left (towards the negative numbers). Find the largest positive integer for which the frog can perform its jumps in such an order that it never lands on any of the numbers .
Solution
Solution:
We claim that the largest positive integer with the given property is , where is by definition the largest integer not exceeding .
Consider a sequence of jumps of length such that the frog never lands on any of the numbers , where . Note that we must have 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 , and the largest jump has length , it is impossible to reach numbers greater than . On the other hand, suppose the frog is in a number , then it must even be in a number , since it is not allowed to hit the numbers . So the frog jumps to the left only if it is in a number , and therefore it is impossible to reach numbers less than . This means the frog only possibly lands on the numbers satisfying
When performing a jump of length , the frog has to remain at either side of the numbers . Indeed, jumping over requires a jump of at least length . In case it starts at a number (in fact ), it lands in and we must also have . So , therefore . In case it starts at a number (in fact ), it lands in and we must also have . Adding to both sides of , we obtain , so in this case we have as well. We conclude that . Since is integer, we even have .
Next we prove that this upper bound is sharp: for the frog really can perform its jumps in such an order that it never lands on any of the numbers .
Suppose is odd, then is an integer and we have , so . We claim that when the frog performs the jumps of length in the following order, it does never land on : it starts with a jump of length , then it performs two jumps, one of length followed by one of length , next two jumps of length and , , next two jumps of length and , , and finally two jumps of length and . In this order of the jumps every length between and does occur: it performs a pair of jumps for , which are the jumps of length and the jumps of length , and it starts with the jump of length .
We now prove the correctness of this jumping scheme. After the first jump the frog lands in . Now suppose the frog is in or and is about to perform the pair of jumps of length and . Starting from , it lands in , after which it lands in . If on the contrary it starts in , it lands in , after which it lands in . We see that, starting in , the frog lands in after the pair of jumps, while starting in the frog lands in , while in both cases the jumps do not touch . This proves the correctness of its series of jumps. As the frog (after its first jump) alternates between and exactly times, for odd it will end up in , while for even it will end up in .
Suppose is even, then is not an integer and we have , so . Let the frog firstly perform the same series of jumps as in the previous case; they still do not touch . Now let the frog make a final extra jump of length . It will land in if is odd, or in if is even, and its series of jumps is correct again.
We conclude that the largest positive integer with the given property is .