1990 IMO SL #18

Let $ a, b \in \mathbb{N}$ with $ 1 \leq a \leq b,$ and $ M = \left[\frac {a + b}{2} \right]$. Define a function $ f: \mathbb{Z} \mapsto \mathbb{Z}$ by \[ f(n) = \begin{cases} n + a, & \text{if } n \leq M, \\ n - b, & \text{if } n >M. \end{cases} \]Let $ f^1(n) = f(n),$ $ f_{i + 1}(n) = f(f^i(n)),$ $ i = 1, 2, \ldots$ Find the smallest natural number $ k$ such that $ f^k(0) = 0$


The answer is $\boxed{a+b}$. 

For now, only consider $\gcd(a,b)=1$. 

Let $S$ be the set of integers such that $$M-b \le x \le M+a-1.$$ Then, $f(S) \subseteq S$ and $0 \in S$ as well. So, this implies $f^k(0) \in S$. Assume that for some $k>0$, we have $f^k(0)=0$. Because $f(m)=m+a$ or $f(m)=m-b$, we know that $k$ can be written as $k=r+s$ where $ra-sb=0$. But $a,b$ are relatively prime, we have $k \ge a+b$. 

We know prove that $k=a+b$ is possible. Namely, we have to prove $f^{a+b}(0)=0$. In this case where $a,b$ are relatively prime, we have $a+b=r+s$, so $$f^{a+b}(0)=(a+b-s)a-sb=(a+b)(a-s)$$. So, because $a+b \mid f^{a+b}(0)$ and $f^{a+b}(0) \in S$, we have $f^{a+b}(0)=0$. 

So, for $\gcd(a,b)=1$, our smallest $k$ satisfying the conditions is $a+b$. For every other pair of $(a,b)$ such that $\gcd(a,b)>1$, note that we get $k=\frac{a+b}{\gcd(a,b)}$, which is why we didn't consider $\gcd(a,b)>1$ in the first place. 

We are done. $\square$

Comments

Popular posts from this blog

1995 IMO #2

Inequality problem I made