Let $n>1 \in \mathbb{N}$ and $a_1, a_2, ..., a_n$ be a sequence of $n$ natural integers. Let: $$b_1 = \left[\frac{a_2 + \cdots + a_n}{n-1}\right], b_i = \left[\frac{a_1 + \cdots + a_{i-1} + a_{i+1} + \cdots + a_n}{n-1}\right], b_n = \left[\frac{a_1 + \cdots + a_{n-1}}{n-1}\right]$$ Define a mapping $f$ by $f(a_1,a_2, \cdots a_n) = (b_1,b_2,\cdots,b_n)$. a) Let $g: \mathbb{N} \to \mathbb{N}$ be a function such that $g(1)$ is the number of different elements in $f(a_1,a_2, \cdots a_n)$ and $g(m)$ is the number od different elements in $f^m(a_1,a_2, \cdots a_n) = f(f^{m-1}(a_1,a_2, \cdots a_n)); m>1$. Prove that $\exists k_0 \in \mathbb{N}$ s.t. for $m \ge k_0$ the function $g(m)$ is periodic. b) Prove that $\sum_{m=1}^k \frac{g(m)}{m(m+1)} < C$ for all $k \in \mathbb{N}$, where $C$ is a function that doesn't depend on $k$.
Problem
Source: Macedonia National Olympiad 2017
Tags: function, algebra
04.06.2017 02:57
Note that $$b_{1} + b_{2} + ... + b_{n} \le \frac{1}{n-1} \cdot ((n-1)a_{1} + (n-1)a_{2} + ... + (n-1)a_{n}) = a_{1} + a_{2} + ... + a_{n}$$That means that the sum of the elements of the sequence is a monovariant. Because the sum of the elements is a natural number, it will reach a minimum number $k$ after a finite number of steps. Afterwards, after every step the sum stays the same because it is non-increasing, and the minimum is already reached. Because the number of different solutions of $$x_{1} + x_{2} + ... + x_{n} = k$$in positive integers is finite, after a finite number of moves after $k$ is reached we will get the same sequence of elements by Pigeonhole principle. This proves that $g(m)$ is periodic. Now for part $b)$, it's easy to see that $g$ being periodic after a fixed $k_{0}$ implies that it takes only finitely many values, so there is a constant $C$ such that $g(n) < C$ for all $n \in \mathbb{N}$. Now we have $$\sum \limits_{m=1}^{k} \frac{g(m)}{m(m+1)} < C \cdot \sum \limits_{m=1}^{k}\frac{1}{m(m+1)} = C \cdot \sum \limits_{m=1}^{k} \left( \frac{1}{m} - \frac{1}{m+1} \right) = C \cdot \left( 1 - \frac{1}{k+1} \right) < C$$$$Q.E.D$$
04.06.2017 06:15
nice solution