Maths Olympiad Prep

Library / /18 of 29

Algebra Difficulty 6.4 National olympiad Prove it Silk Road Mathematics Competition

Let 0<a<b<10 < a < b < 1 be real numbers and
g(x)={x+1a,if 0<x<a,ba,if x=a,xa,if a<x<b,1a,if x=b,xa,if b<x<1. g(x) = \begin{cases} x + 1 - a, & \text{if } 0 < x < a, \\ b - a, & \text{if } x = a, \\ x - a, & \text{if } a < x < b, \\ 1 - a, & \text{if } x = b, \\ x - a, & \text{if } b < x < 1. \end{cases}
Assume that for some positive integer nn there are n+1n+1 real numbers 0<x0<x1<<xn<10 < x_0 < x_1 < \dots < x_n < 1 such that gn(xi)=xig^n(x_i) = x_i for 0in0 \le i \le n. Prove that there is a positive integer NN such that gN(x)=xg^N(x) = x for all 0<x<10 < x < 1. (Notation: gk(x)=g(g((g(x))))k timesg^k(x) = \underbrace{g(g(\dots(g(x))\dots))}_{k \text{ times}}).

Solution

For real numbers rr and ss we call them equivalent (and write rsr \equiv s), if rsZr - s \in \mathbb{Z}. Then,
g(x){xa,if x≢a,b,ba,if xa,a,if xb. g(x) \equiv \begin{cases} x - a, & \text{if } x \not\equiv a, b, \\ b - a, & \text{if } x \equiv a, \\ -a, & \text{if } x \equiv b. \end{cases}
Note that gg is a bijection on (0,1)(0,1). Let
S={gi(a):0in1}{gi(b):0in1}. S = \{g^{-i}(a) : 0 \le i \le n-1\} \cup \{g^{-i}(b) : 0 \le i \le n-1\}.
Then gn(x)=xnag^n(x) = x - na for xSx \notin S.
Case 1. gng^n has a fixed point xx' outside SS.
Then xgn(x)xnax' \equiv g^n(x') \equiv x' - na, and therefore, na0na \equiv 0 and gn(x)=xg^n(x) = x for all xSx \notin S. On the other hand, gng^n is a permutation of SS, and for some positive integer mm, (gn)m(g^n)^m be the identity in SS. So we can take N=mnN = mn in this case.
Case 2. All fixed points of gng^n are in SS.
If g(a)Sg(a) \notin S, then none of gi(a)g^{-i}(a) for 0in10 \le i \le n-1 can be a fixed point of gng^n, and gng^n can not have more than nn fixed points. Similarly, g(b)Sg(b) \notin S is impossible. Therefore, g(S)=Sg(S) = S. In particular, as in Case 1, there is a positive integer mm such that gnm(x)=xg^{nm}(x) = x for all xSx \in S.
Since g(S)=Sg(S) = S, gng^n is a bijection on (0,1)S(0,1)\setminus S. As gng^n is defined by xxnax \to x - na on (0,1)S(0,1)\setminus S, it means that xxnax \to x - na is also bijection on SS. It follows that lna0lna \equiv 0 for some positive integer ll, and therefore gnl(x)=xg^{nl}(x) = x for all xSx \notin S.
Hence we can choose N=nmlN = nml in this case.

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 and solution reproduced as published; topic and difficulty added by this site.