Problem

Source: Macedonia National Olympiad 2017

Tags: function, algebra



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$.