Европейская математическая олимпиада среди девочек (EGMO). 2017 год. Швейцария

Натурал $k$ саны үшiн келесi екi шартты қанағаттандыратын:
   (i) $f(m+n)=f(m)+f(n)$ теңдiгi кез келген бiр түстi натурал $m$, $n$ сандары үшiн орындалады;
   (ii) $f(m+n) \neq f(m)+f(n)$ теңсiздiгi орындалатындай $m$, $n$ натурал сандары табылады;
   натурал сандарының $\mathbb{N}$ жиыны $k$ түске бояуы және $f:\mathbb{N} \to \mathbb{N}$ функциясы табылады. $k$ санның ең кiшi мәнiң табыңыз.
   Натурал сандары $\mathbb{N}$ жиынының $k$ түске бояғанда әр сан $k$ түстен тек бiр түске боялған. (i) және (ii) шарттарда $m$, $n$ натурал сандары тең болуы да мүмкiн.

Комментарий/решение

Ответ: $k=3$

Оценка снизу:

Заметим что из второго условие $k>1$. Допустим существует раскраска черным и белым цветом которое удовлетворяет условие. Назовем число $k$ линейным если $f(k)=kf(1)$. Тогда так как $f(2m)=2f(m)$, если $m$ линейный то $2m$ тоже линейный. Возьмем $x$ как наименьшее число которое не в множестве линейных чисел. Тогда все числа $1,…,x-1$ являются линейными. Заметим что если для какого то $f(j)+f(x-j)=f(x)$ то $x$ линейный что невозможно. Значит $\forall j$ и $x-j$ имеют различные цвета. Заметим что x-нечетный а то иначе $f(x)=2f(\frac{x}{2})=cx$. Из того что $x \geq 3$, f(x+1)=c(x+1). Если $x$ и $x-1$ разных цветов тогда $f(1)+f(x)=f(x+1)$ и отсюда $x$ линейный что невозможно. Если $x+1$ и $x$ разных цветов тогда f(x+1)+f(1)=f(x+2) значит $x+2$ линейный. Но тк $x$ и $2$ одного цвета ( иначе $x$ и $x-2$ одного цвета и $f(x-2)+f(x)=f(2x-2)=2f(x-1)$ что следует к линейности $x$) отсюда $f(2)+f(x)=f(x+2)$ что тоже невозможно. Значит $x-1, x, x+1$ одного цвета: $f(x+1)+f(x-1)=f(2x)=2f(x)$ что следует к линейности $x$.

Суммируя мы доказали что каждое число является линейным что противоречит второму условию.

Пример на $k=3$:

Возьмем $f(n)=\dfrac{n}{3}$ для $3 |n$ и $f(n)=n$ для остальных. И тогда раскрасим числа в три цвета их остатков по моду $3$.