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

Найдите наименьшее положительное целое число $k$, для которого существуют: раскраска положительных целых чисел $\mathbb{Z}_{ > 0}$ в $k$ цветов и функция $f: \mathbb{Z}_{ > 0} \rightarrow \mathbb{Z}_{ > 0}$, удовлетворяющая следующим двум условиям:
   (i) Для всех положительных целых чисел $m, n$ одинакового цвета $f(m+n)=f(m)+f(n)$.
   (ii) Найдутся положительные целые числа $m, n$ такие, что $f(m+n) \neq f(m)+f(n)$.
   В раскраске $\mathbb{Z}_{ > 0}$ в $k$ цветов каждое целое число окрашено ровно в один из $k$ цветов. В условиях (i) и (ii) положительные целые числа $m, n$ не обязательно различны.

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

Ответ: $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$.