Maths Olympiad Prep

Library / /152 of 299

Algebra Difficulty 6.5 National Olympiad Prove it Iran

Let 12<s<1\frac{1}{2} < s < 1. An insect jumps on points in the interval [0,1][0, 1]. If the insect is on point aa, it can jump to either s×as \times a or (a1)×s+1(a - 1) \times s + 1. Prove that for any arbitrary point cc in the interval [0,1][0, 1], the insect can jump in such a way that after a few steps, it will be at a distance less than 11402\frac{1}{1402} from cc.

Solutions — 2

Solution 1

We call the number xx an nn-digit number if it can be written as x=i=0naisix = \sum_{i=0}^{n} a_i s^i where 0in\forall 0 \le i \le n, aia_i is either 00 or 1s1-s (note that ana_n can be 00 too). Using the operations presented in the problem, starting from aa, we can obtain numbers of the form asN+ba s^N + b where bb can be any (N1)(N-1)-digit number. For any c1c \le 1 and ϵR+\epsilon \in \mathbb{R}^+ we are looking for b,Nb, N such that:
(asN+b)c<ϵ |(a s^N + b) - c| < \epsilon
To prove this, it is sufficient to find bb such that bc<ϵ|b-c|<\epsilon and then choose sufficiently large NN to satisfy the inequality.
We will prove by induction that for every c1c \le 1 there exists an nn-digit number like bb such that
bc<sn1 |b-c| < s^{n-1}
This obviously proves the main statement.
For the base of the induction, n=1n=1 is obvious. Now let's assume the statement holds for nn. We will prove it also holds for n+1n+1. If c>1sc > 1-s we define c=c(1s)sc' = \frac{c-(1-s)}{s}. This number is in the interval [0,1][0,1] because:
c(1s)s1    c1s+s=1 \frac{c - (1 - s)}{s} \le 1 \iff c \le 1 - s + s = 1
By the induction hypothesis there exists an nn-digit number bb such that:
c(1s)sbsn1    c((1s)+s×b)sn \left| \frac{c - (1 - s)}{s} - b \right| \le s^{n-1} \implies \left| c - \left( (1 - s) + s \times b \right) \right| \le s^n
However 1s+s×b1 - s + s \times b is an (n+1)(n+1)-digit number. If c1sc \le 1 - s then we define c=csc' = \frac{c}{s} this number is also in the interval [0,1][0, 1] because:
c1ss    c1 c \le 1 - s \le s \implies c' \le 1
Then by the induction hypothesis there exists an nn-digit number bb such that:
csbsn1    cs×bsn |\frac{c}{s} - b| \le s^{n-1} \implies |c - s \times b| \le s^n
Here s×bs \times b is an (n+1)(n+1) digit number. Thus the inductive step is proven. The proof is now complete.

Solution 2

f(x)=sx,g(x)=sx+1s. f(x) = s x, \quad g(x) = s x + 1 - s.
We know that the images of functions f,gf, g on [0,1][0, 1] are [0,s][0, s] and [1s,1][1 - s, 1], respectively. It is clear that the length of each interval is ss and the union of them is [0,1][0, 1].
At each time, the position of the insect can be obtained from the compositions of f,gf, g. Hence, the possible positions of her after nn steps would be of the form h1(h2((hn(x))))h_1(h_2(\dots(h_n(x)\dots))), where hi{f,g}h_i \in \{f, g\}. It turns out that the length of the interval of each such function is sns^n.
We then prove by induction that for each nn the union of the images of these intervals covers [0,1][0, 1]. The base is true. Assume that the statement holds true for all integers don't exceed kk. Hence, the images of all possible compositions h1(h2((hk(x))))h_1(h_2(\dots(h_k(x)\dots))) covers [0,1][0, 1]. Notice that image of any of h1(h2((hk(g(x)))))h_1(h_2(\dots(h_k(g(x))\dots))) or h1(h2((hk(f(x)))))h_1(h_2(\dots(h_k(f(x))\dots))) covers the image of h1(h2((hk(x))))h_1(h_2(\dots(h_k(x)\dots))). this completes our proof.
Now, suppose a point a[0,1]a \in [0, 1]. We shall then prove that there is a positive integer nn that the image of h1(h2((hn(x))))h_1(h_2(\dots(h_n(x)\dots))) contains aa. For this reason, choosing nn such that 12022>sn\frac{1}{2022} > s^n it follows that the insect shall be in the interval of (a12022,a+11402)(a - \frac{1}{2022}, a + \frac{1}{1402}). We are done. ■

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.