Maths Olympiad Prep

Library / Silk Road Mathematics Competition competition problems /16 of 25

Silk Road Mathematics Competition competition problems

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+1−a,if 0<x<a,b−a,if x=a,x−a,if a<x<b,1−a,if x=b,x−a,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 0≤i≤n0 \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 r≡sr \equiv s), if r−s∈Zr - s \in \mathbb{Z}. Then,
g(x)≡{x−a,if x≢a,b,b−a,if x≡a,−a,if x≡b. 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={g−i(a):0≤i≤n−1}∪{g−i(b):0≤i≤n−1}. S = \{g^{-i}(a) : 0 \le i \le n-1\} \cup \{g^{-i}(b) : 0 \le i \le n-1\}.
Then gn(x)=x−nag^n(x) = x - na for x∉Sx \notin S.
Case 1. gng^n has a fixed point x′x' outside SS.
Then x′≡gn(x′)≡x′−nax' \equiv g^n(x') \equiv x' - na, and therefore, na≡0na \equiv 0 and gn(x)=xg^n(x) = x for all x∉Sx \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 g−i(a)g^{-i}(a) for 0≤i≤n−10 \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 x∈Sx \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 x→x−nax \to x - na on (0,1)∖S(0,1)\setminus S, it means that x→x−nax \to x - na is also bijection on SS. It follows that lna≡0lna \equiv 0 for some positive integer ll, and therefore gnl(x)=xg^{nl}(x) = x for all x∉Sx \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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.