Each positive integer is coloured red or blue. A function $f$ from the set of positive integers to itself has the following two properties: (a) if $x\le y$, then $f(x)\le f(y)$; and (b) if $x,y$ and $z$ are (not necessarily distinct) positive integers of the same colour and $x+y=z$, then $f(x)+f(y)=f(z)$. Prove that there exists a positive number $a$ such that $f(x)\le ax$ for all positive integers $x$. (United Kingdom) Ben Elliott
Problem
Source: Romanian Master Of Mathematics 2012
Tags: function, algebra proposed, algebra, combinatorics, combinatorics proposed, Additive combinatorics
enescu
03.03.2012 23:58
http://rmm.lbi.ro/index.php?id=solutions_math Edit: the address is now http://rmms.lbi.ro/rmm2012/index.php?id=solutions_math
manif0ld_
16.12.2012 01:22
If there does not exist a positive number $a$ such that $f(x)<ax$ for all positive integers $x$ then there are positive integers $\alpha$, $x$,$y$, and $z$ such that $x+y = z, f(x) \leq \alpha x, f(y) \leq \alpha y,$ and $f(z) > \alpha z.$ But then we have $\alpha (x+y) > f(z) = f(x) + f(y) \leq \alpha x + \alpha y = \alpha (x+y). \ _\Box$
Adrienmath
05.10.2014 19:26
manif0ld_ wrote: If there does not exist a positive number $a$ such that $f(x)<ax$ for all positive integers $x$ then there are positive integers $\alpha$, $x$,$y$, and $z$ such that $x+y = z, f(x) \leq \alpha x, f(y) \leq \alpha y,$ and $f(z) > \alpha z.$ But then we have $\alpha (x+y) > f(z) = f(x) + f(y) \leq \alpha x + \alpha y = \alpha (x+y). \ _\Box$ And ?
yugrey
10.12.2014 03:34
Here is my not very well LaTexed solution: Recall the statement. We have this coloring s.t. x,y,x+y same color -> f(x+y)=f(x)+f(y) where f:Z+->Z+. Lemma: We have that we do not have arbitrarily large runs of red in a row. Proof is that if we did, then if m is the smallest and n is a bigger red, runs of mn give that f(n)=(n/m)*f(m). So in this case f(x)<=ax for red x. Now, if for any sufficiently large blue b we have that at least one of b+1,...2b are red, then f(x)<=2a*x and we win. Else we have arbitrarily long blues in a row and similarly we're done. So we can WLOG we have only finitely many reds in a row and similarly finitely many blues. For any N we can have the same about 0 mod N guys because it's the same condition. Great. Now, define a number X to be irreducible iff we cannot split it into m,n with m+n=X and both of m,n>.01*X where m,n,X are the same color. Oh, let C be such that x,x+1,...x+C are never all the same color. I claim all these can be irreducible for only finitely many x (this is Lemma 2). If not, for some 0<k<C we have WLOG that x is red, x+k is blue for infinitely many x. So take some r==0 mod k red, such that r is between .09*x and .91*x (if we cannot find this for sufficiently large x, we can an arbitrarily large blue run of 0 mod k and it's GG). We have that x-r is blue so r+k is red. Doing this we get arbitrarily large red runs of 0 mod k and it's GG. So Lemma 2 is proved. Now, let's describe an algorithm. Originally, f(x)<=K*x, looking at the first bunch of values. We look at enough starting values such that whenever I have said "for all but finitely many" it covers all those finitely many. We are going to keep modifying the constant, initialized to K, with the following process: Whenever we reach an X that's irreducible with f(X)>KX, we multiply K by (X+C)/X. This works because for some s<=C we have f(X+s)<=K*(X+s), since X+s is reducible and splits into things less than X (yeah, I should say X is sufficiently large here... we start this process at a big enough finite place). So f(X)<=K*(X+C) easily meaning this is going to work. Great, call X a "modifying point" r. So we have that the constants are in total multiplied by (1+C/r) over all these modifying points r. Using e^y>=1+y it suffices to prove sum 1/r over all these modifying points r converges. Assume X is a modifying point and Y is also where y<1.00001*x. Also, say that f(x)<=K_1*x for all x<X was the constant we used before x, and f(x)<=K_2*x was the constant we used for x. We have that some value Y<Z<=Y+C that Z is reducible, so f(Z)<=K_1*Z for this z. It follows f(Y)<=K_1*(Y+C)<=K_2*Y, because K_2/K_1>=(X+C)/X>=(Y+C)/Y since Y>=X, and C/X>=C/Y. So then Y isn't actually a sticking point, contradiction. It follows that sum 1/r limit compares to sum 1/(1.00001)^t over all positive integers t which converges, gg.
Moubinool
08.09.2020 17:43
this is Romanian master competition 2012 problem day 1 , problem 3 http://rmms.lbi.ro/rmm2012/index.php?id=solutions_math
Aryan-23
20.09.2020 00:46
Nice problem, but I think it's quite easy if someone has seen IMO 2010/6. Since we are provided with seemingly too much less information, we want to exploit the pseudo Cauchy behaviour as much as possible. This suggests looking at "monochromatic blocks" of the form $[n,n+m]$ which maintain constant $\frac {f(x)}{x}$ ratio . I think for these kind of "Pseudo cauchy" problems, considering the behavior of ratios (f(x)/x) is quite helpful in general (it was almost destined to work for this problem). Some other tropes useful for this problem: once we have $r_1+r_2=b_1+b_2$, this means that either $f(r_1)+f(r_2)=f(r_1+r_2)$ or $f(b_1)+f(b_2)=f(b_1+b_2)$. This is quite robust and this means if all the block lengths are bounded above and we could enumerate the start points of the red as $r_{\bullet}$ (resp blue), then we have :
$$f(r_x+b_y-1)= \{f(r_x)+f(b_y-1), f(r_x-1)+f(b_y)\}$$Not very hard from here
Note that if all the red numbers satisfied $\frac {f(r)}r=c_r$ (and resp blue ,with constant being c_b) , then we could just take $\operatorname {max} ( c_r,c_b)$. Assume that is not the case.
Define a monochromatic block to be of the form $[n,n+mn]$. Then it's easy to get for any such block we have $\frac {f(m)}{m}=\frac {f(n)}n$.
Suppose that for some color (WLOG red), the monochromatic blocks are unbounded. So $f(r)=cr$ for all red $r$. Now consider the case if the monochromatic blocks for the blue numbers were also bounded. We'd easily get $f(b)=db$ for all blue $b$ and win by the previously made remarks. Hence consider the case , that there exists a $C$ such that any block of the form $[b,b+C]$ with $b$ is a blue number is not monochromatic. We are again done by the non-decreasing condition in this case.
Henceforth we assume that $\exists M$ such that the monochromatic blocks have length atmost $M$. Hence we can enumerate the starting points of each monochromatic block as $1=r_1<b_1<r_2<b_2\dots$. Now pick some $m$ such that $b_m-1>M$. Note that we have
$$f(r_k+b_m-1)= \{f(r_k)+f(b_m-1), f(r_k-1)+f(b_m)\} \quad \forall k\geq 2$$
This gives $$\operatorname {max}(f (r_{i+1}),f (r_{i+1})-1) \leq f(r_i+b_m-1) \leq \operatorname {max}(f (r_{i}),f (r_{i})-1)+ \operatorname {max}(f (b_{m}),f (b_{m})-1)$$
Hence $\exists \alpha$ such that $f(r_n) \leq \alpha n$. We are done by $\frac {f(n)}{n}\le \frac {f(r_n)}{n} \le \alpha$.
Number1048576
14.02.2024 19:45
We first show that there cannot be arbitrarily long contiguous blocks of either colour.
Assume the opposite - that there are arbitrarily long contiguous blue blocks. Let $j$ be the smallest blue number.
Then for each $k$ blue sufficiently large, we will show that $f(k) \le k(\frac{f(j)}{j}+1)$.
Take $n$ such that $n,\cdots,n+k+j+1$ are all red. Then $f(n+j\lceil \frac{k}{j} \rceil) = f(n) + f(j)\lceil \frac{k}{j} \rceil$. However, $f(n+k) < f(n+j\lceil \frac{k}{j} \rceil)$, so $f(k) = f(n+k) - f(n) < f(j)\lceil \frac{k}{j} \rceil < k \frac{f(j)}{j} + f(j) < k(\frac{f(j)}{j}+1)$ for $k$ sufficiently large, as required.
Hence, there cannot be arbitrarily long contiguous red blocks as well as otherwise $\frac{f(x)}{x}$ is bounded above for all $x$.
Say that the longest contiguous red block has length $L$.
Then for every sufficiently large $k$ there is $x \le L+1$ such that $f(k+x) < (k+x)(\frac{f(j)}{j}+1) \implies f(k) < (k+L)(\frac{f(j)}{j}+1) \le k(\frac{f(j)}{j}+2)$ for $k$ sufficiently large, a contradiction.
Let the longest contiguous block of either colour have length $L$.
We now show that for every $k$ there are infinitely many pairs $(x,y)$ such that $x$ is red, $y$ is blue, and $y-x = k$.
Consider the numbers which are multiples of $k$. If only finitely many are red, then there is a number $T$ such that all multiples of $k$ at least $T$ (where $T$ is a multiple of $k$) are blue, but then $f(nT) = nf(T)$, which gives a contradiction similarly to before.
However, if infinitely many are red, then only finitely many can be blue as otherwise there are infinitely many such pairs, but then we get a contradiction similarly to before.
Now, let $N$ be a number such that for all $\ell \le 100L$, there are at least $100L$ pairs $(x,y)$ where $x$ is red, $y$ is blue, $y \le N$ and $y - x = \ell$, and for which there are at least $100L$ pairs $(x,y)$ where $x$ is blue, $y$ is red, $y \le n$ and $y - x = \ell$.
We will show that for all $n$, $f(n+1) - f(n) \le f(N)$, which suffices.
Say that there are two blue numbers $x$, $y$ such that there is no blue number in between $x$ and $y$, and that $f(y) - f(x) > f(N)$.
Let $w$ be the largest red number smaller than $x$. Note that if there is $L+1 < u < N$ such that $u$ is blue and $f(x+u)$ is blue, then $f(y) \le f(x+u) = f(x) + f(u) \le f(x) + f(N) \implies f(y) - f(x) \le f(N)$, a contradiction.
Similarly, if there is $3L < u < N$ such that $u$ is red and $f(w+u)$ is red, then $f(y) \le f(w+u) = f(w) + f(u) \le f(x) + f(N)$, which is again a contradiction. Now, take a pair $(u,v)$ with $u$ blue, $v$ red, $v-u=x-w$ and $u > 3L$. Then $x+u$ cannot be red, but $w+v = x+u$ cannot be blue. However, $x+u$ must be either blue or red, and so $f(y) - f(x) \le f(N)$, which implies that for all $n$, $f(n+1) - f(n) \le f(N)$, and so we are done.
IAmTheHazard
19.02.2024 20:20
First suppose that there exist arbitrarily large red intervals. Pick any two red integers $a, b$ and consider a red interval $[M,M+ab]$. We should have $$f(M)+af(b)=f(M+b)+(a-1)f(b)=\cdots=f(M+ab)=f(M+ab-a)+f(a)=\cdots=f(M)+bf(a),$$hence $f(x)=cx$ for some $c>0$ on the red integers. The symmetric result holds for blue intervals. Thus if there exist arbitrarily large monochrome intervals of both colors we are immediately done. If there only exist arbitrarily large monochromatic intervals of one color—WLOG red—then there exists some $t>0$ such that blue intervals contain at most $t$ integers, and now $f(x) \leq c(x+t)$ in general if $f(x)=cx$ over red $x$, which also finishes. Hence suppose there exists some integer $T>0$ such that monochromatic red or blue intervals contain at most $T$ integers. Lemma: For any $2T+1$ consecutive positive integers, there exist $r_1,r_2$ red and $b_1,b_2$ blue among them such that $r_1+r_2=b_1+b_2$. Proof: If we can find two non-adjacent numbers of the same color (WLOG red) $a,b$ such that every $a<x<b$ is blue, we are done, since $a+b=(a+1)+(b-1)$ and $a+1$ and $b-1$ (not necessarily distinct) are blue by definition. If we split our $2T+1$ consecutive integers into maximal monochromatic "blocks", we need at least $3$ blocks since each block is at most $T$ integers long. Hence the rightmost number in the first block and the leftmost number in the third block will work. $\blacksquare$ For nonnegative integers $n$ let $g(n)$ denote the maximum of $\frac{f(t)}{t}$ for $1 \leq t \leq \lfloor 1.5^n\cdot 1000T\rfloor$; clearly it suffices to show that $g$ is bounded above. This will follow from the following key claim after some algebra. Claim: We have $$g(n+1) \leq g(0)\prod_{i=0}^n \left(1+\frac{4T+1}{1000T}1.5^{-i}\right)$$Proof: Pick some $\lfloor 1.5^n \cdot 1000T\rfloor<t \leq \lfloor 1.5^{n+1}\cdot 1000T\rfloor$. Let $m=\lceil t/2\rceil$; by the lemma there exist red $r_1,r_2$ and blue $b_1,b_2$ among $\{m,\ldots,m+2T\}$ such that $r_1+r_2=b_1+b_2:=k$, so $$t \leq 2m \leq k \leq 2m+4T \leq t+4T+1.$$Now, regardless of the color of $k$, we have $$\frac{f(k)}{k} \leq \max\left(\frac{f(r_1)}{r_1},\frac{f(r_2)}{r_2},\frac{f(b_1)}{b_1},\frac{f(b_2)}{b_2}\right) \leq g(n),$$since we have $m+2T \leq \lfloor 1.5^n \cdot 1000T\rfloor$. Thus $$f(t) \leq f(k) \leq kg(n) \implies \frac{f(t)}{t} \leq \frac{k}{t}g(n) \leq \left(1+\frac{4T+1}{1.5^n\cdot 1000T}\right)g(n),$$so $g(n+1)$ is at most the RHS since $t$ is arbitrarily chosen. This finishes by induction. $\blacksquare$ Since $g(0)$ is finite, it suffices to show that $$\prod_{i=0}^\infty \left(1+\frac{4T+1}{1000T}1.5^{-i}\right)$$converges. Since every term is at least $1$, by taking logs it suffices to show that $$\sum_{i=0}^\infty \ln \left(1+\frac{4T+1}{1000T}1.5^{-i}\right)$$converges. Using the well-known inequality $\ln(1+x) \leq x$, it suffices to show that $$\sum_{i=0}^\infty \frac{4T+1}{1000T}1.5^{-i}$$converges, which is obviously true. $\blacksquare$