Крашеная функция

[Nikys]

Каждое натуральное число покрашено красным или синим цветом. Функция определена на множестве натуральных чисел и принимает натуральные значения, и удовлетворяет следующим условиям:
а) если $x \leq y$, то $f(x) \leq f(y)$,
б) если $x$,$y$ и $z$ - (необязательно разные) натуральные числа одного цвета и $x+y=z$, то $f(x)+f(y)=f(z)$.
Доказать, что существует такое положительное число $a$, что $f(x) \leq ax$ для всех натуральных $x$.

(Оффтоп)

V Румынская международная мат.олимпиада, 2012 год
Чисто авторское решение не предлагать :)

[Dave]

Пусть $f(4)=b$. Докажем по индукции, что при любом целом неотрицательном $n$: $f(2^n+3) \leqslant 2^nb$. При $n=0$ утверждение очевидно. Допустим, что оно верно при $n=m$. Тогда, в силу условия а), $f(2^m+1) \leqslant f(2^m+2) \leqslant f(2^m+3) \leqslant 2^mb$. Среди чисел $2^m+1, \, 2^m+2, \, 2^m+3$ найдутся хотя бы два покрашенных в один цвет. Если $x$ и $y$ - такие числа, то $z=x+y \geqslant 2^{m+1}+3$ и в силу п. б) и, опять же, п. а), $f(2^{m+1}+3) \leqslant f(z)=f(x)+f(y) \leqslant 2^mb+2^mb=2^{m+1}b$, т.е. утверждение доказано для $n=m+1$.
Если теперь $x$ - любое натуральное число и $\lceil \log_2 x \rceil=n$, то $n-1 < \log_2 x \leqslant n$, $2^{n-1}<x \leqslant 2^n<2^n+3$, значит, по доказанному утверждению и в силу п. а), $f(x) \leqslant f(2^n+3) \leqslant 2^nb=2b2^{n-1}<2bx$, т.е. $a=2b$ подходит в качестве требуемого числа.

[Dave]

Пардон, ошибся в том, что $f(z)=f(x)+f(y)$, ведь $z$ может быть другого цвета. Придётся несколько усложнить решение.
Случай, когда один из цветов не используется - тривиальный, функция $f$ будет линейной ввиду $f(x+1)=f(x)+f(1) \Rightarrow f(x)=xf(1)$, поэтому считаем, что присутствуют числа обоих цветов.
Назовём цвет популярным, если существуют отрезки натуральных чисел сколь угодно большой длины, покрашенные только этим цветом.
Если цвет $A$ - популярный, а $m$ и $n$ - любые числа, покрашенные этим цветом, то, выбрав отрезок $r,r+1,r+2,\dots,r+mn$, покрашенный цветом $A$, получим, в силу условия б):

$$f(r+mn)=f(r+m(n-1))+f(m)=f(r+m(n-2))+f(m)+f(m)=\dots=f(r)+nf(m),$$

$$f(r+mn)=f(r+n(m-1))+f(n)=f(r+n(m-2))+f(n)+f(n)=\dots=f(r)+mf(n),$$

откуда получаем, что $\frac {f(m)} m = \frac {f(n)} n$, т.е. функция $f$ линейна на числах цвета $A$: $f(x)=k_Ax$ для всех $x$ цвета $A$.
Отсюда следует, что если оба цвета - популярные, то $f(x) \leqslant \max \{k_A,k_B\} \, x$, если только один цвет $A$ - популярный; а второй, $B$, - нет и $n$ - длина максимального отрезка цвета $B$, то если $x$ - любое число, покрашенное в цвет $B$, то среди чисел $x+1,x+2,\dots,x+n$ найдётся хотя бы одно, пусть это будет $y$, покрашенное в цвет $A$. Очевидно, $y \leqslant x+n \leqslant (n+1)x$. И, по условию а), $f(x) \leqslant f(y) =k_Ay \leqslant k_A(n+1)x$, т.е. можно взять $a=k_A(n+1)$.
Осталось рассмотреть случай, когда ни один из цветов не является популярным. Пусть $n$ - длина максимального отрезка, покрашенного одним цветом. Пусть также $b=f(3n+1)$. Докажем по индукции, что при любом неотрицательном целом $z$: $f(2^z+3n) \leqslant 2^zb$. При $z=0$ утверждение очевидно. Пусть оно верно при $z=m$. Докажем его для $z=m+1$. Среди чисел $2^{m+1}+3n,2^{m+1}+3n+1,\dots,2^{m+1}+4n$ найдётся пара чисел разных цветов, а значит и пара соседних чисел разных цветов. Пусть меньшее из них равно $t$ и покрашено в цвет $A$, а большее равно $t+1$ и покрашено в цвет $B$. Пусть также $d=\left[ \frac t 2 \right]$. Тогда $2^m+n \leqslant d \leqslant t-d \leqslant 2^m+2n$. Докажем, что среди чисел диапазона $D=\{2^m,2^m+1,\dots,2^m+3n\}$ найдётся пара $(x,y)$, такая, что число $z=x+y$ равно либо $t$, либо $t+1$ и вcя тройка $(x,y,z)$ покрашена в один и тот же цвет.
Предположим противное и рассмотрим два случая. Если $d$ - цвета $A$, то $t-d$ должно быть цвета $B$, $(t+1)-(t-d)=d+1$ - цвета $A$, $t-(d+1)=t-d-1$ - цвета $B$ и т.д. В конце концов мы придём к тому, что $n$ чисел $t-d,t-d-1,t-d-2,\dots,t-d-(n-1)$, всё еще находящихся в диапазоне $D$, - цвета $B$, а $n+1$ число $d,d+1,d+2,\dots,d+n$, опять же из $D$, - цвета $A$, что противоречит определению $n$. Если же $d$ - цвета $B$, то $(t+1)-d=t-d+1$ должно быть цвета $A$, $t-(t-d+1)=d-1$ - цвета $B$, $(t+1)-(d-1)=t-d+2$ - цвета $A$ и т.д. В конце концов мы придём к тому, что $n$ чисел $t-d+1,t-d+2,t-d+3,\dots,t-d+n$, всё еще находящихся в диапазоне $D$, - цвета $A$, а $n+1$ число $d,d-1,d-2,\dots,d-n$ - цвета $B$, что опять же противоречит определению $n$.
Доказанное утверждение позволяет завершить доказательство по индукции, ибо

$$f(2^{m+1}+3n) \leqslant f(t) \leqslant f(z)=f(x)+f(y) \leqslant f(2^m+3n)+f(2^m+3n) \leqslant 2 \cdot 2^mb=2^{m+1}b.$$

А дальше так: если $x$ - любое натуральное число и $\lceil \log_2 x \rceil=h$, то $h-1 < \log_2 x \leqslant h$, $2^{h-1}<x \leqslant 2^h<2^h+3n$, значит, по доказанному утверждению и в силу п. а), $f(x) \leqslant f(2^h+3n) \leqslant 2^hb=2b \cdot 2^{h-1}<2bx$, т.е. $a=2b$ подходит в качестве требуемого числа.

[Dave]

Предлагаю ответить на вопрос:

Верно ли утверждение задачи, если в п. б) равенство $f(x)+f(y)=f(z)$ заменить на неравенство $f(z) \leqslant f(x)+f(y)$ ?

[Nikys]

Dave

(Оффтоп)

Пока нет времени это решить, срочно разбираю завалы в учебе после командировки. Скорее всего, к завтрашнему вечеру займусь этим вопросом, т.к. буду сравнительно свободен. Но мое предположение пока что, что утверждение останется в силе.

[Dave]

Dave в сообщении #546409 писал(а):

Предлагаю ответить на вопрос:

Верно ли утверждение задачи, если в п. б) равенство $f(x)+f(y)=f(z)$ заменить на неравенство $f(z) \leqslant f(x)+f(y)$ ?

Сделаю подсказку: утверждение неверно. Приведите пример, доказывающий это.