Let . An insect jumps on points in the interval . If the insect is on point , it can jump to either or . Prove that for any arbitrary point in the interval , the insect can jump in such a way that after a few steps, it will be at a distance less than from .
Solutions — 2
Solution 1
We call the number an -digit number if it can be written as where , is either or (note that can be too). Using the operations presented in the problem, starting from , we can obtain numbers of the form where can be any -digit number. For any and we are looking for such that:
To prove this, it is sufficient to find such that and then choose sufficiently large to satisfy the inequality.
We will prove by induction that for every there exists an -digit number like such that
This obviously proves the main statement.
For the base of the induction, is obvious. Now let's assume the statement holds for . We will prove it also holds for . If we define . This number is in the interval because:
By the induction hypothesis there exists an -digit number such that:
However is an -digit number. If then we define this number is also in the interval because:
Then by the induction hypothesis there exists an -digit number such that:
Here is an digit number. Thus the inductive step is proven. The proof is now complete.
Solution 2
We know that the images of functions on are and , respectively. It is clear that the length of each interval is and the union of them is .
At each time, the position of the insect can be obtained from the compositions of . Hence, the possible positions of her after steps would be of the form , where . It turns out that the length of the interval of each such function is .
We then prove by induction that for each the union of the images of these intervals covers . The base is true. Assume that the statement holds true for all integers don't exceed . Hence, the images of all possible compositions covers . Notice that image of any of or covers the image of . this completes our proof.
Now, suppose a point . We shall then prove that there is a positive integer that the image of contains . For this reason, choosing such that it follows that the insect shall be in the interval of . We are done. ■