IMO

# USA December TST for IMO 2017

Problems from AoPS.

Q1. In a sports league, each team uses a set of at most $t$ signature colors. A set $S$ of teams is color-identifiable if one can assign each team in $S$ one of their signature colors, such that no team in $S$ is assigned any signature color of a different team in $S$.

For all positive integers $n$ and $t$, determine the maximum integer $g(n, t)$ such that: In
any sports league with exactly $n$ distinct colors present over all teams, one can always
find a color-identifiable set of size at least $g(n, t)$.

Q2. Let $ABC$ be an acute scalene triangle with circumcenter $O$, and let $T$ be on line $BC$ such that $\angle TAO = 90^{\circ}$. The circle with diameter $\overline{AT}$ intersects the circumcircle of $\triangle BOC$ at two points $A_1$ and $A_2$, where $OA_1 < OA_2$. Points $B_1$, $B_2$, $C_1$, $C_2$ are defined analogously.

1. Prove that $\overline{AA_1}$, $\overline{BB_1}$, $\overline{CC_1}$ are concurrent.
2. Prove that $\overline{AA_2}$, $\overline{BB_2}$, $\overline{CC_2}$ are concurrent on the Euler line of $ABC$. (E. Chen)

Q3. Let $P, Q \in \mathbb{R}[x]$ be relatively prime nonconstant polynomials. Show that there can be at most three real numbers $\lambda$ such that $P + \lambda Q$ is the square of a polynomial. (A. Miller)

Standard
IMO

# China National Maths. Olympiad 2016 – 17

1. Define sequence $u_0 = u_1 =1, u_n =2u_{n-1}-3u_{n-2}$ for $n \ge 2$. Define $v_0 = a, v_1 =b, v_2 =c, v_n = v_{n-1}-3v_{n-2}+27v_{n-3}$ for $n \ge 3$. Suppose that there exists $N \in \mathbb N^+$ such that $\forall n \ge N$, $u_n | v_n$. (In particular this implies $v_n \texttt{'}$s are integers for large enough $n$.) Show that $3a = 2b +c$.
2. In scalene $\triangle ABC$, $I$ is the incentre. (I.e. centre of incircle.) The tangents at $B$ and $C$ to the circumcircle of $\triangle ABC$ intersect at $L$. The incircle touches the side $BC$ at $D$. Drop perpendicular from $A$ to $BC$, intersecting $BC$ at $Y$. $AO$ intersects $BC$ at $X$. Let line $OI$ intersect the circumcircle of $\triangle ABC$ at $P,Q$. Show that: $A,D,L$ are colinear if and only if $P,Q, X, Y$ are con-cyclic.
3. Let $\mathcal R$ be a closed rectangle. Let $\mathcal R$ be dissected into $2016$ smaller rectangles, whose sides are parallel to either side of $\mathcal R$. The vertices of the smaller rectangles are called ‘nodes‘. A segment (which must be part of the partition) joining two nodes is called a basic segment if it contains no nodes other than its two endpoints. Find the maximum number and minimum number of basic segments across all dissecting configurations.
4. Let integer $n \ge 2$. For two permutations of $\{1,2, ..., n\}$: $\alpha = (a_1, a_2, ..., a_n)$ and $\beta = (b_1, b_2, ... , b_n)$, we call them turnings of each other, if there exists positive integer $k \le n$ such that $\\ b_i = a_{k+1-i} \,\,\,\,\, 1\le i \le k; \\ b_i = a_i\,\,\,\,\, k < i \le n \,$. Prove:It is possible to arrange all permutations of $\{1,2,...,n\}$ into a sequence $P_1, P_2, ... P_{n!}$ such that for all $i = 1,2, ..., n!$, $P_i$ and $P_{i+1}$ are turnings of each other. Here we let $P_{n!+1}=P_1$.
5. Let $\mathcal {D}_n$ denote the set of all positive integral divisors of positive integer $n$. Find all positive integer $n$ such that $\mathcal {D}_n$ can be written as the union of two DISJOINT subsets $\mathcal {A}$ and $\mathcal G$, which satisfy : $|\mathcal A| \ge 3, |\mathcal G|\ge 3$, the elements of $\mathcal A$ can be arranged into an arithmetic progression, and the elements of $\mathcal G$ can be arranged into a geometric progression.
6. Let $n\ge 2$ be a given integer. Let $a,b$ be two given positive numbers with $a. Suppose real numbers $x_1, x_2, ... x_n \in [a,b]$, find the maximum value of

$\displaystyle \frac {\frac{x_1^2}{x_2}+\frac{x_2^2}{x_3}+ ... +\frac{x_{n-1}^2}{x_n}+\frac{x_n^2}{x_1}}{x_1 + x_2 + ... + x_{n-1}+x_n}$.

Q1. My friend Jongmin Lim sent me the following solution. I have been working on it for a a rather extended period, but I constrained myself into a suboptimal approach that proved ultimately unsuccessful.

BTW this Jongmin dude did the IMO at some point in his life. Got 23/42, i.e. barely passed. But the IMO, currently being inundated with people from scrub countries, has a compromised awarding scheme, in which someone who did slightly better than barely passed can be awarded a silver medal; and upon the OP, who, despite his friendship with Jongmin, is consistently scrub-like in Olympiad problem solving, and who almost hit the 50% line but, notwithstanding the maximal effort from Team Leader and Deputy Leader which earned him marks that the OP is not sure whether he would have received without being from an Anglophone country with a respectable Leader, did not quite, a bronze medal is bestowed to signify that fact that he could solve the easiest problems and did not black out on the problems that are more becoming of the IMO’s prestige.

So the problem gave us recursions, linear recursions which we can actually solve. Whenever such thing comes around, solving it is never a bad idea because it doesn’t take up much time and it can be illuminating.

$\displaystyle u_n=\frac{(1+\sqrt 2 i)^n+ (1-\sqrt 2 i)^n}{2}, v_n = \alpha 3^n + \beta (-1+2\sqrt 2 i)^n+\gamma(-1-2\sqrt 2 i)^n$.

Okay… We see that, if we denote $\lambda = 1+\sqrt 2 i, \bar \lambda = 1-\sqrt 2 i$, we have $\lambda ^2 = -1+2 \sqrt 2 i, \bar \lambda ^2 = -1-2\sqrt 2 i, \lambda \bar \lambda = 3$. Thus the two recursions are related in such a superficial way.

Since we have constructed three new parameters, we can express $a,b,$ and $c$ in terms of them. The conclusion, in new parameters, read: $3(\alpha + \beta + \gamma) = 2(3\alpha + (-1+2\sqrt 2 i)\beta + (-1-2\sqrt 2 i)\gamma)+ 9 \alpha + (-7 - 4 \sqrt 2 i)\beta + (-7 + 4\sqrt 2 i)\gamma \implies \alpha = \beta + \gamma$. This looks a lot nicer.

The ‘eventually integer’ condition says a lot. We wish to exploit it.

$\displaystyle \frac{v_n}{u_n}= \frac {2(\alpha - \beta -\gamma)3^n}{\lambda ^n + \bar \lambda ^n}+ 2(\beta \lambda ^n + \gamma \bar \lambda ^n)$. This transformation is crucial: it mimics the long division algorithm and  permits separate treatment of the remainder from the main part of the quotient.

We of course wish to have $2(\beta \lambda ^n +\gamma \bar \lambda ^n)$ is an integer and the other term, the remainder, to be disallowed from being an integer for very large $n$ and thus to establish that the remainder is zero always. But that is not easy: how are we going to establish that the main part is an integer at all? It does indeed remind us of the $v_n$ recursion itself, but the $3^n \alpha$ term is not at all easy to deal with.

Well, we shall have a closer look at the $v_n$ because we have not really used the integer condition yet. We have that $v_n \in \mathbb Z$ for all large $n$, from which we wish to recover, at least, the rationality of $\alpha, \beta, \gamma$.

So we let $n$ be large and choose three consecutive values of $n$ to start with.

$3^n \alpha + \lambda ^{2n} \beta + \bar \lambda ^{2n} \gamma \in \mathbb Z; \\ 3^{n+1} \alpha + \lambda ^{2n+2} \beta + \bar \lambda ^{2n+2} \gamma \in \mathbb Z; \\ 3^{n+2} \alpha + \lambda ^{2n+4}\beta + \bar \lambda ^{2n+4} \gamma \in \mathbb Z.$

No matter what the RHS is, we have a linear system in $[\alpha, \beta, \gamma]$ with coefficients in $\mathbb Z [\sqrt {-2}]$. We thus wish to make further compromise and settle to prove that $\alpha, \beta, \gamma \in \mathbb Q [\sqrt{-2}]$.

To do that, we only have to show that the coefficient matrix has non-zero determinant.

But a matrix with the first column $3^n[1,3,3^2]^T$, second column $\lambda ^{2n}[1,\lambda ^2, (\lambda^2)^2]^T$, third column $\bar \lambda^{2n} [1, \bar \lambda ^2, (\bar \lambda ^2)^2]^T$has its determinant the form of a Vandermonde matrix, which vanishes if and only if the common ratios of two of its geometric progressions are equal. In this case we thus have a non-zero determinant and thus $\alpha, \beta, \gamma \in \mathbb Q [\sqrt{-2}]$.

That wasn’t too bad. But how to proceed?

Key insight: the denominator of the rational number $\displaystyle \frac{3^n (\alpha - \beta -\gamma)}{u_n}$ is unbounded. This is because: $3\not | u_n, \forall n$. This is because, modulo $3$, $u_{n+1}\equiv -u_n$. Now, since $u_0 = u_1 = 1$, $u_n$ is never a multiple of $3$. We need to show that $u_n$ is unbounded. We will do that at the end of the proof. This is how we wish to establish the remainder is non-integer after all. Therefore it only remains to show that $\beta \lambda ^{2n} + \gamma \bar \lambda ^{2n}$ has bounded denominator when written in simplest form to finish off the problem. (This is where I made the mistake, I strove to demonstrate that it is an integer, but bounded denominator suffices.)

Since $\beta$ and $\gamma$ are both in $\mathbb Q [\sqrt{-2}]$, and $\lambda, \bar \lambda \in \mathbb Z [\sqrt{-2}]$, we actually have that happening. Explicitly, for $r+q\sqrt{2} i$, where $r,q \in \mathbb Q$, $r= \frac {\sigma_1}{\zeta_1}, q = \frac {\sigma_2}{\zeta_2}$ are called simplest form if $|\sigma|+|\zeta|$ is minimised. We write it in simplest form, and define $f(r+q\sqrt 2 i) = \textnormal{lcm} (\zeta _1, \zeta _2)$. It is easy to verify that multiplying an element in $\mathbb Q [\sqrt {-2}]$ by an element in $\mathbb Z [\sqrt{-2}]$ does not increase its $f$-value. Thus the $f$ value of $2\beta \lambda ^n + 2\gamma \bar \lambda ^n$ is bounded. We are done, as for large value of $n$, $\frac {v_n}{u_n}$, has one component whose denominator is very large, thus not an integer.

Wait! I promised to show that $u_n$ is unbounded, now it is time to actualise my promise. $\displaystyle u_n = \Re ((1+\sqrt 2 i)^n) = \cos (\arg ((\frac{1}{\sqrt 3}+\frac{\sqrt 2}{\sqrt 3} i)^n))(\sqrt 3 )^n = (\sqrt 3)^n \cos (n\arccos (\frac {1}{\sqrt 3}))$. Therefore it suffices for the problem to show that there exists a sequence $y_n \in \mathbb N^+$ such that $\displaystyle |\cos (\arccos (\frac {1}{\sqrt 3})y_n)|$ is lower bounded. That can be accomplished by showing the existence of infinitely many $y_n$ such that $\displaystyle \arccos{\frac{1}{\sqrt 3}}y_n$, when divided by $2\pi$, gives off a remainder that is within the interval $\displaystyle [0, \arccos (\frac{1}{\sqrt 3})]$.

Suppose that $\displaystyle \frac {\arccos (\frac {1}{\sqrt 3})}{2\pi} \in \mathbb Q$, $\displaystyle 2\pi |\arccos (\frac{1}{\sqrt 3}) y_n$ happens for $y_n$ in an arithmetic progression. Suppose that  $\displaystyle \frac {\arccos (\frac {1}{\sqrt 3})}{2\pi}= \eta$ is an irrational number, the sequence $\{\eta n\}$ is dense in $[0,1)$, where $\{x\}$ denotes the fractional part of $x$. In particular, this shows the existence of infinitely many $y_n \in \mathbb N^+$ such that $\displaystyle \{\frac {\arccos (\frac{1}{\sqrt 3})y_n}{2\pi} \}\in [0,\frac {\arccos (\frac{1}{\sqrt 3})}{2\pi}]$, or, $\displaystyle \cos (\arccos (\frac{1}{\sqrt 3})y_n) \in [\frac {1}{\sqrt 3}, 1]$. This shows that $u_{y_n} \ge (\sqrt 3)^{y_n-1}$ which goes to infinity for large $y_n$.

Q5. This is all my own work, and I started writing this up as soon as I finished solving this problem by brute force base bash. I believe that while it might not be the most economical method, it is instructive to write up the most natural instinct when the problem is encountered. There are problems — e.g. IMO 2015 Q2, proposed by Dusan Djukic — for which no quick or enlightening methods exist. In such cases, as one is generally never informed of whether the problem he encounters is of this class, it is important to be able to bash. If any improvement on the bash method can be proposed, I will also include it as an alternative. For papers like IMO 15′ day 1, the contestants are discriminated by their ability to finish off bashing work efficiently and correctly. Many well-trained, talented contestants could not perform the bashing perfectly and got 6/7.

Standard
IMO

# Iran TST 2011 Q5

Find all SURJECTIVE functions $f:\mathbb R \to \mathbb R$ such that $\forall x,y \in \mathbb R$,

$f(x+f(x)+2f(y))=f(2x)+f(2y)$.

Answer: $f(x)=x, \forall x \in \mathbb R$.

Let the equation be $P(x,y)$.

All right… Surjective… That means we will be able to let $f(y)$ be whatever we want…

$f(x)=x$ obviously works, and $f(x)=kx, k\ne 1$ don’t work. $f(x)=x+c,c\ne 0$ don’t work either. Since the right hand side is symmetric in $x$ and $y$, we’d expect the LHS to be basically symmetric as well (hmm we might be able to twiddle take this, at some point), thus we expect $f(x)=x$ to be the only solution. (Constant solutions work but they are not surjective.

Turns out that $x+f(x)$ term is hard to control, and we don’t find $f(0)$ that easily.

We want to show it is injective. Because if it was injective we can twiddle take the equation and show $f(y)-f(x)=y-x$ by switching $y$ and $x$, from which the solution follows straightaway.

So LHS, as function of $y$ only depends on $f(y)$, and the RHS has only $f(2y)$. Thus we see that $f(2y) = h(f(y))$, i.e. $f(2y)$ only depends on $f(y)$.

Now, let $f(x_1)=f(x_2)$, then $P(x_1,y), P(x_2,y) \implies f(x_1 + f(x_1)+2f(y))=f(x_2 + f(x_1)+2f(y))$ as $f(2x_1)=f(2x_2)$. Let $x_1 - x_2 = t, 2f(y)+f(x_1)+x_2 = a$. We then have $f(a+t)=f(a), \forall a \in \mathbb R$. (This uses surjectivity!!!! It is only because the function is surjective that we can make $a$ range over the entire real number.)

Seems like our injectivity scheme is not going well… Well we will twiddle take the equation anyway.

Define $x\equiv y$ as $f(x)=f(y)$. That is, $x-y$ is a period of $f$. It is easy to check that this is an equivalence relation that is preserved by addition of equal term.

$P(x,y). P(y,x) \implies x+f(x)+2f(y) \equiv y+f(y) + 2f(x)$, or,

$(f(x)-x) \equiv (f(y)-y) , \forall x, y \in \mathbb R \,\,\,\,\,\,\,(*)$.

This is like a pseudo $f(y)-f(x)=y-x$….  Let’s sub in values and see…

Let $f(r)=0$. (by surjectivity it exists.)

In (*) let $y=0$, we see that $f(x)\equiv x+f(0)$.

$P(0,r) \implies f(f(0))=f(0)+f(2r)$. LHS$\equiv f(0)+f(0)\equiv 2f(0)$, RHS$\equiv f(0)+2r+f(0)$. Thus $2r \equiv 0$.

$P(r,y) \implies f(r+f(r)+2f(y))=f(2r)+f(2y)$. $P(0, y) \implies f(0+f(0)+2f(y))=f(0)+f(2y)$. Since $2r \equiv 0$, $r \equiv f(0) \equiv f(f(r)) \equiv r + 2f(0)$. Thus $2f(0)\equiv 0$.

$\displaystyle P(\frac r2 , y) \implies f(\frac r2 +f(\frac r2 )+2f(y))=f(2y) \\ \implies \frac r2 +f(\frac r2 )+2f(y) \equiv 2y \\ \implies 2\times \frac r2 + f(0) + 2y + 2f(0) \equiv 2y \\ \implies r \equiv -f(0) \equiv f(0)\\ \implies 0=f(r) =f(f(0))$.

But since $r \equiv f(0), 2r \equiv r+r\equiv f(0)+f(0)\equiv 2f(0)\equiv 0$, thus $f(f(0))=f(0)+f(2r)=2f(0)$. But $f(f(0))=0 \implies f(0)=0$.

So, we tried to show that $f$ is injective, but ended up showing $f(0)=0$. That is still great though, because now we have $f(x)\equiv x, \forall x \in \mathbb R$. All these substitutions are found by trial and error, which makes the problem quite challenging indeed. The idea behind, though, is that if the “$\equiv$” sign is replaced by equal, we will be able to determine $f(0)=0$ by equating coefficients of LHS and RHS of $P(x,y)$. We are just doing in modulo the set of periods.

Since $f(f(x))=f(x)$, all values in the image of $f$ are fixed points of $f$.

But $f$ is surjective. Thus $f(\mathbb R)=\mathbb R$, thus every real number is a fixed point. Or, $f(x)=x, \forall x \in \mathbb R$.

Comment: the middle part of finding the $f(0)$ is tricky, and it is useful to notice the structure that all difference between pair of number giving off the same value are periods of the function. We used the surjectivity twice, once when showing that they are periods, the other when showing that the image of $f$ is the entire real number. The second time, despite that the equation could be reduced to additive Cauchy function, the zero function can still work, so we need to use the surjectivity to do this.

Standard
IMO

# Online Algebra Olympiad 2016 Q5

Find all $f: \mathbb R \to \mathbb R$ such that $f(xf(x)-yf(y))=f(x-y)(f(x)+y),\forall x,y \in \mathbb R$.

All right, looks old-fashioned. For old-fashioned functional equation whose solutions are probably only the obvious ones, we aim to characterise its properties instead of its specific values. Sleeves up, let’s get to work.

Answer: $f(x)=0, \forall x \in \mathbb R$ and $f(x)=x, \forall x \in \mathbb R$.

(Checking is omitted for it is trivial.)

Let $S_2 = \{x\in \mathbb R | f(f(x))=x \}, \Omega = \{x \in \mathbb R | f(x)=0\}$, and $P = \{x \in \mathbb R | f(t)=f(t+x), \forall t \in \mathbb R\}$.

That is, $S_2, \Omega, P$ are sets of second-order fixed points, zeroes, and periods of the function, respectively. We will see why we mentioned these sets very soon.

Let the statement of the question be $P(x,y)$. The condition looks rather symmetric, but not quite. This gives us space for manipulation.

$P(0,0) \implies f(0)=f(0)^2 \implies f(0)= 0$ or $1$.

Having conjectured that only the two aforementioned solutions to the functional equation exist, we aim to rule out the second case.

$P(x,x) \implies f(0)=f(0)(f(x)+x) \implies f(x)=1-x$. Substitution shows that this is NOT a solution. Thus $f(0)=0$.

Keep going, we are on track.

$P(0,y) \implies f(-yf(y)) = yf(-y), P(0,-y) \implies f(yf(-y))=-yf(y)$.

Look, look, these two switch between each other. Better take this information into account. $\forall y \in \mathbb R, -yf(y), yf(-y) \in \mathbb S_2$.

But how are we going to exploit the second order fixed points? We have to substitute it into somewhere and compare it with the original value, so we’d better do it with something where $x$ and $f(x)$ are both present, as in such occasion substituting $s \in S_2$ will make this expression comparable with the original one. Such expression exists in the LHS.

$P(s,f(s)), s \in S_2 \\ \implies f(sf(s)-f(f(s))f(s))=f(s-f(s))(f(s)+f(s))\\ \implies f(s-f(s))f(s)=0$,

as $f(f(s))=s$ and $f(0)=0$. If $s \ne 0$, $f(s) \ne 0$ as $f(f(s))=s \ne 0$ and $f(0) =0$. Thus $f(s-f(s)) =0$. If $s=0$, $f(s-f(s))= f(0-0)=0$. Thus in whatever case, $s-f(s) \in \Omega$.

Look at that. That looks like quite some information isn’t it, especially after we substitute $s= yf(-y)$ in…

$yf(-y)-f(yf(-y))=yf(-y)+yf(y) = y(f(y)+f(-y)) \in \Omega, \forall y \in \mathbb R$.

That wasn’t a big surprise, since the $y$ and $-y$ are supposed to either cancel or both give vanishing function value anyway. But this expression has an advantage….

$P(x, -x) =\implies f(xf(x)+xf(-x))=f(2x)(f(x)-x)$, and the LHS of this expression is equal to $0$. Thus,

$\forall x \in \mathbb R, f(2x)=0$ or $f(x)=x \ \ \ \ \ \ \ \ \ \ \ \ \ (*)$.

Once we are here normally there are many ways to finish the problem off.

Claim: $\Omega = P$.

If $p \in P$, $f(p)=f(0+p)=f(0)=0$.

If $\omega \in \Omega. P(\omega, -y)\implies f(yf(-y))=f(\omega +y)(0+y)=yf(\omega +y)$. $P(0,-y) \implies f(yf(-y)) = f(y)y$. If $y \ne 0$, we can divide both sides by $y$ and conclude $f(\omega + y) =\frac {f(yf(-y))}{y} = f(y)$. If $y =0$, $f(\omega + y) = f(\omega) =0 =f(0)=f(y)$. Thus $f(\omega + y)=y, \forall y\in \mathbb R$.

If $f$ only vanishes on $x=0$, we recall the statement (*), in which $f(2x) \ne 0, \forall x \ne 0$, thus $f(x)=x \forall x \in \mathbb R \ \{0\}$. But $f(0)=0$ anyway, thus $f(x)=x$.

If $\exists \omega \ne 0, f(\omega)=0$, then $\omega$ is a period of the function. $P(x, \omega) \implies f(xf(x))=f(x-\omega)(f(x)+\omega)=f(x)(f(x)+\omega)=f(x)^2 +\omega f(x)$.

But now, $P(x, 0) \implies f(xf(x))=f(x)^2$. Thus $\omega f(x)=0, \forall x \in \mathbb R$. Which, since $\omega \ne 0$, forces us to have $f(x)=0, \forall x \in \mathbb R$.

Comment: Boring problem, just a few substitutions to crack it open. But the substitutions are not that easy to find, especially the middle part where one needs to play around with the second order fixed point set. The part proving that all zeroes are periods makes use of the ubiquity of $f(x)$ on both sides (since it is ubiquitous we let it vanish to reduce the equation down.)

Standard
IMO

# China TST 14′ Q3 & USA TSTST 12′ Q3

Suppose $f:\mathbb N^+ \to \mathbb N^+$ satisfies:

1) $\gcd(f(m),f(n))\le \gcd (m,n)^{2014},\forall m,n\in \mathbb N^+$

2) $n\le f(n)\le n+2014,\forall n \in \mathbb N^+$.

Show that $\exists \Omega \in \mathbb N^+,f(n)=n, \forall n \ge \Omega$.

Let $\mathcal B = \{n\in \mathbb N^+ | f(n) \ne n\}$.

The $2014$ looks DAUNTING. Let’s try a small case with both the $2014$‘s replaced with $1$.

If $\exists n$ large enough, $f(n)=n+1$, we will need $f(n+1)=n+2$ because if $f(n+1)=n+1$, we will have $\gcd(f(n+1),f(n))=\gcd(n+1,n+1)=n+1 > \gcd(n+1,n)=1$ which is bad. Therefore we inductively show that all large enough $n$ will have $f(n)=n+1$. Then we will choose large enough odd $n$ and $n+2$, and thus $f(n)=n+1$ and $f(n+2)=n+3$, which blows up the inequality 1) by $\gcd (f(n),f(n+2)) =2 \ge \gcd(n,n+2)=\gcd(n,2)=1$

Right. We have a rough idea now: letting infinitely many non-fixed points exist and then we show that there are A LOT of non-fixed points, in which set we can do stuff. Note that the above ‘very large’ only requires $n+1 > 1$.

Choose $\Omega = 2014^{2014} +1$. We claim that  $\forall n\in \mathcal B, n \le 2014 ^{2014}$.

We suppose it is not true, and let $q \ge \Omega$ and $q\in \mathcal B$, with $f(q)=q+c$.

We want to control $\gcd(f(n),q+c)$ and $\gcd(n,q)$ at the same time, thus we want to use Chinese Remainder Theorem to get a good residue modulo $q$ and $q+c$. But CRT requires co-primality of the different modulos that we are putting together, thus $\gcd(q,q+c)=\gcd(q,c)=g \le 2014$, because $1\le c \le 2014$.

Let $\displaystyle \frac ng \equiv g \mod \frac qg$,

$\displaystyle \frac ng \equiv 0 \mod \frac {q+c}{g}$. (This can be done now by definition of $g$.)

We claim that for such $n$, $n \in \mathcal B$.

Because if not, $\gcd(f(n),f(q))=f(q+c,n)=q+c$, and $\gcd (n,q)=g$. The second equation is true because if $g|q$, we have $\gcd(n,q)=\gcd(n,g)=g$. If $g \not | q$, we then have $\displaystyle \gcd (n,g\frac qg)=\gcd (\frac ng,\frac qg)g=\gcd(1,\frac qg)g=g$. We thus need $g^{2014} \ge q+c$ which is not true as $g^{2014} \le 2014^{2014}$ and $q+c > \Omega > 2014 ^{2014}$.

(This is why we defined $\Omega$ to be that number !!!)

Thus we see that there exists an infinite arithmetic progression whose large enough terms are all elements of $\mathcal B$. We will just write $\mathcal A$ for the arithmetic progression.

We now want to let ($a\in \mathcal A$) $f(a)=a+k$ have prime factors that we push to infinity, whereas $a$ themselves must not be tainted with those factors. And then we will compare it with other stuff, with the ‘other stuff’ better be coprime with $a$, with $f(\textnormal {other stuff})$ having enough common factor with $f(a)$ to blow up the inequality. (Don’t say this word at airport.)

Choose $p_{i,j}$, where $i \in \{1,2, ... , 2014\}, j\in \{0,1,...,2014\}$ to be a collection of $2014 \times 2015 = 4058210$ different primes which are all greater than $2014$ and all greater than the common difference in $\mathcal A$. This can be done as there are infinitely many primes. (Yes, infinitude of primes is a GREAT theorem. It gives you a nice collection of modulos to Chinese Remainder on. And Chinese Remainder theorem is used almost always to only show the existence of a certain desired solution taking the form of an A.P., while not accentuating on the numerial value of the solution.)

Let

$\displaystyle \\ \eta \in \mathcal A \\ \\ \eta \equiv -1 \mod p_{1,j}, \forall j, \\ \\ \eta \equiv -2 \mod p_{2,j}, \forall j, \\ \\ ... \\ \\ \eta \equiv -i \mod p_{i,j}, \forall j, \\ \\ ... \\ \\ \eta \equiv -2014 \mod p_{2014, j}, \forall j .$

We need to show that this can be done. All we need to show is that all the $p_{i,j}$‘s are coprime to the common difference of $\mathcal A$, which is true since we have chosen them to be large enough.

(This step is why we took all the pain to show that elements of $\mathcal B$ not only exist, but exist IN AN ARITHMETIC PROGRESSION, and then we can select the desired subsequence we want from it by Chinese Remaindering the arithmetic progression with other prime modulos. Only assuming that $\mathcal B$ has infinitely many elements restricts what we can do on it.)

Note that what we are doing now DEVIATES from what we did with the simple case, because now it is rather difficult to control over what happens to $f(\eta)$ as now we only have $f(\eta) \ne \eta$ instead of what it actually is. Thus I wish to restrict all the values of $f(\eta)$ and then compare it with OTHER positive integer’s function values instead of integers in the arithmetic progression that defined $\eta$.

Fix the $\eta$, and suppose $f(\eta) = \eta +c$, where $1\le c \le 2014$.

Now let

$\displaystyle \sigma \equiv - j \mod p_{c,j}$ for each $p_{c,j}, 0\le j \le 2014$.

and $\sigma \equiv 1 \mod \eta$.

Again, we need to show that this can be done, and it suffices to check that $\gcd (\eta, p_{c,j})=1, \forall p_{c,j}$. Assume this is not true, and $p_{c,\rho} | \eta$. Recall that $\eta + c \equiv 0 \mod p_{c,\rho}, \implies \gcd(\eta, \eta+c) =\gcd(\eta, c) \ge p_{c, \rho}$.

The above inequality is impossible due to the fact that $p_{c,\rho} > 2014 \ge c >0$. Thus the Chinese Remainder construction of $\sigma$ is indeed possible. (Note that the $c>0$ requires the full power of $\eta \in \mathcal B$.)

OMG SO MANY CHINESE REMAINDERS… We use it to control the remainders of the variables dividing each other so as to manipulate the gcd’s.

Finally, we have an $\eta \in \mathcal B$ with all its possible function values being star-crossed, and a $\sigma$, not necessarily in $\mathcal B$, with all its function values holding such an enmity with function values of $\eta$. This will blow up the inequality.

Substitute $\eta$ and $\sigma$ into the inequality, $\implies \gcd(f(\eta),f(\sigma)) \le \gcd (\eta, \sigma)^{2014}$. The RHS $=1$ as $\sigma \equiv 1 \mod \eta$. The LHS $= \gcd (\eta +c, \sigma + k)$, where $0 \le k \le 2014$, and since $p_{c,k} | \eta+c, p_{c,k} | \sigma + k$, LHS $\ge p_{c,k} >1$. Contradiction.

Comment: while the idea is easy, it takes great care to babysit all the details in the Chinese Remainder Constructions, as one easily runs into modulos not being coprime or remainder actually $\equiv 0$ which must be evaded if we wish to estimate the gcd. All the first half is done to generate an A.P. of $\mathcal B$‘s elements. I admit it can be annoying to see such problem posed in an exam, but we now see that all the crazy and daunting $2014$‘s are indeed red herrings (its status of red herring should be apparent on first glance), the factor that really matters here is the FINITENESS of all the indices, for which a Chinese Remainder will always work because we only need finitely many congruence equations to hold simultaneously–and we can use A LOT of difference congruence equations to make our life easy as there’s not taxation on considering  many congruence equations at the same time.

Suppose $f:\mathbb N^+ \to \mathbb N^+$ satisfies:

1) $\gcd(f(m),f(n))=1$ if and only if $\gcd (m,n)=1$

2) $n\le f(n) \le n+2012.$

Show that $\forall n\in \mathbb N^+, \forall p$ prime, $p|f(n)$ implies $p|n$.

This problem seems to be the precursor of the one in 2014, and is left to the reader as an exercise.

Standard
IMO

# IMO 2013 Q5

Suppose $f:\mathbb Q^+ \to \mathbb R$ satisfies:

1. $f(x)f(y)\ge f(xy),\forall x,y\in \mathbb Q^+$
2. $f(x+y)\ge f(x)+f(y),\forall x,y \in \mathbb Q^+$
3. $\exists a \in \mathbb Q^+, a >1, f(a)=a.$

Show that $f(x)=x,\forall x \in \mathbb Q^+.$

All right. This looks like a spin-off of Cauchy equation, which, when fixed on rational numbers, admits only trivial solutions, and the deduction is done by first doing it on integers and then extending it to rational numbers.

The codomain being $\mathbb R$ hints that it is not advisable to iterate the function. We might want to perform preliminary investigation on it first.

Let the condition 1 be $P(x,y)$, condition 2 be $Q(x,y)$.

$P(1,a) \implies f(1) f(a) \ge f(a)$, or, $f(1)a \geq a$. Thus, $f(1) \geq 1$, since $a>0$.

$Q(n-1,1) \implies f(n)\ge f(n-1)+f(1)\ge f(n-1)+1$. This can be used to inductively prove that $f(n) \ge n,\forall n \in \mathbb N^+$.

$P(\frac mn , n)\implies f(\frac mn)f(n)\ge f(m)\ge m$. Since $f(n) >0, f(\frac mn)\ge \frac m{f(n)}>0,$ where $m,n \in \mathbb N^+$, and $\frac mn \in \mathbb Q^+.$

Let $x_1 < x_2, x_1, x_2 \in \mathbb Q^+, Q(x_1, x_2-x_1)\implies f(x_2)\ge f(x_1)+f(x_2 - x_1) > f(x_1).$ Thus $f$ is strictly monotically increasing.

That was the (trivial) preliminary investigation. We have obtained some upper bounds on the function’s values at integers, but further investigation seems beyond reach. This is because we cannot really find any upper bound on the function values $f(x)$ that does not involve further reference to function values.

(In fact, at this point, if the fixed point condition is ignored, $f(x)=x^2$ fits into all the above equations. I did not realise this when I attempted the problem, but it does, in hindsight, point at the necessity of utilising the fixed point condition.)

$P(a, a^{k-1})\implies f(a^{k-1})a\ge f(a^k)$. This can be used inductively to prove that $a^k \ge f(a^k)$.

YES! I has it! Upper bound! From now on we will just try to compare the function value with the powers of $a$ in order to apply a sandwich squeezing type of idea to fix the $f(x)$ because we were worried about $f$ growing too rapidly.

Claim: $\forall x \in \mathbb Q^+, f(x) \le x$.

Fix $\lambda \in \mathbb Q^+$. We define $l(x) = \left\lfloor \frac x \lambda \right\rfloor \lambda$, and $u(x)= \left\lceil \frac x \lambda \right\rceil \lambda$. We thus have $0\le u(x)-x < \lambda, 0\le x-l(x) < \lambda$.

(Here we are defining extensions of floor and ceiling functions.)

Let $h:\mathbb N^+ \to \mathbb Q^+$ be $h(k)=a^{k+1} - a^k$, and $g:\mathbb N^+ \to \mathbb Q^+$ be $g(k) = l(a^{k+1})-u(a^k)$. Let $k\to \infty$, as since $a>1$, we have $g(k) \to \infty$. We will let $k$ be large enough such that $g(k) >0$. Thus $h(k) \ge g(k)$, from which $\displaystyle \frac {f(h(k))}{f(g(k))}\ge 1$.

$\displaystyle Q(h(k),a^k)\implies f(a^{k+1}-a^k) + f(a^k) \le f(a^{k+1}) \\ \implies f(h(k))\le f(a^{k+1})-f(a^k)\\ \le af(a^k)-f(a^k) =(a-1)f(a^k) \le (a-1)a^k \\ =h(k) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (*)$

as $f(a^{k+1}) \le af(a^k)$ and $f(a^k)\le a^k$

At this point we are still extending the property of $a$ to obtain more points with $f(x)\le x$. But the next inequality involves the idea of approximating the “$a$ polynomials” with “multiples” of $\lambda$. The approximation idea is why we defined that generalisation of floor and ceiling function in the first place: we cannot use $a$‘s polynomials to attack $\lambda$ straightaway, we then do it approximately and then analysis will take care of the error.

On the other hand,

$\displaystyle P(\frac{g(k)}{\lambda},\lambda)\implies \\ f(g(k))\ge f(\frac{l(a^{k+1})-u(a^k)}{\lambda})f(\lambda)\\ \ge \frac{g(k)}{\lambda}f(\lambda) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (**)$

as $\frac {l(a^{k+1})-u(a^k)}{\lambda} \in \mathbb N^+$ (by the definition of $l(x)$ and $u(x)$, and our choice of $k$ being large enough), and the fact that $f(n)\ge n, \forall n\in \mathbb N^+$.

Dividing (*) by (**) (as both inequalities have their both sides positive), we get

$\displaystyle \frac {f(h(k))}{f(g(k))}\le \frac{\lambda}{f(\lambda)} \frac{h(k)}{g(k)} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (!)$.

The equation (!) is our main breakthrough. We will very soon let both sides tend to their limit as $k\to \infty$, thus the inequality will practically look like $1\le \frac {\lambda}{f(\lambda)}$

Thus it only remains to show that both $\lim _ {k \to \infty} \frac {h(k)}{g(k)}=1$ and $\lim _ {k\to \infty} \frac{f(h(k))}{f(g(k))}=1$. The first one: $0\le h(k)-g(k) < 2\lambda$, thus $\frac { h(k)-g(k) }{g(k)}<\frac {2\lambda}{g(k)}$. Now let $g(k)\to \infty$ shows that $\lim _{k \to \infty}\frac { h(k)-g(k) }{g(k)}=0$.

If we consider the worse case scenario, $h(k)-g(k)>0$. But if the worse case does not happen, substituting $h(k)-g(k)$ into the functional inequality is illegitimate.

If $h(k)>g(k)$, $Q(h(k)-g(k),g(k))\implies 0< f(h(k))-f(g(k)) \le f(h(k)-g(k)) < f(2\lambda)$. (The last inequality is true by the monotonicity of $f$ !) If $h(k)=g(k)$, $f(h(k))-f(g(k))=0<2\lambda$.

In either case, $f(h(k))-f(g(k)) \in [0,2\lambda]$ is inevitable.

This is the approximation idea at work. We have successfully controlled the error uniformly. We only need to show that $f(g(k)) \to \infty$ as $k\to \infty$ to establish the claim.

But this is obvious since $f(g(k))\ge \frac {g(k)}{\lambda} f(\lambda)$ (As $\frac{g(k)}{\lambda}\in \mathbb N^+$, and $f(qn) \ge nf(q),\forall n\in \mathbb N^+$ . And now $g(k)>(a-1)a^k -2\lambda \to \infty$ as $k\to \infty$, our claim is proven.

We already have $f(n)\ge n, \forall n\in \mathbb N^+$, and thus we automatically have $f(n)=n,\forall n\in \mathbb N^+$.

$P(\frac mn , n) \implies nf(\frac mn) \ge f(m)=m$. Thus $f(\frac mn ) \ge \frac mn$. This combined with the claim, which requires $f(\frac mn) \le \frac mn$, gives $f(\frac mn)=\frac mn ,\forall m,n\in \mathbb N^+$.

Q.E.D.

Standard
IMO

# Renhui Jiuzhang 2015 Exam 1 Q3

Suppose $f:\mathbb Z \to \mathbb Z$ satisfy $f(x-f(y))=f(x)^2+f(2x-f(y)),\forall x,y \in \mathbb Z,$ show that $f(f(x))=0,\forall x \in \mathbb Z.$

From this post on I will try to adopt a more casual tone in expounding the solution, with explanatory text mixing with the solution.

First, we see that the equation does not easily lead itself to non-trivial solution (the $f(x)^2$ term is quite weird), therefore we decide to punish it by repeatedly substituting different values of variables until we can compare the information about the values to find a contradiction.

Setting $x=0, f(-f(y))=f(0)^2 + f(-f(y))$, and cancelling gives $f(0)=0$.

Let $y$ be any integer, substituting $x=f(y)$ will give us $f(0)=f(f(y))^2+f(f(y)).$ Since the LHS vanishes, we thus have $f(f(y))=0$ or $-1,\forall f\in \mathbb Z$. Thus we only have to rule out the latter case and the proof is complete.

Notice that the functional equation, though strange in $\mathbb Z$, behaves benignly when only the parity is concerned: in fact, setting $f(x)=x$, we have a ‘solution’ to it $\mod 2$. Thus we want to consider parity. Setting $y=0$, we have $f(2x)= f(x)-f(x)^2.$ The RHS, incidentally, is always an even number, whereas the LHS is the function value of any even number. Thus $f$ maps even numbers to even numbers. (Note that the same cannot be said of odd numbers as $f(x)=0$ is a solution to the equation.)

We aim to utilise the assumption that $\exists \xi \in \mathbb Z, f(f(\xi))=-1.$ We let $f(\xi)=\eta$, for convenience. Let $y=\xi$ in the original equation, we obtain $f(x-\eta)=f(x)^2+f(2x-\eta)$. Now we implant our initial strategy of trashing the function with repeated substitutions.

Let $x=\eta, y=0$, we find $f(2\eta)=f(\eta)-f(\eta)^2 = -1-1=-2.$ Setting $x=2\eta,y=\xi$, we thus have $f(\eta)=f(2\eta)^2+f(3\eta),$ thus $f(3\eta)= -1 -(-2)^2 =-5$ . We thus know that $-1,-2$ and $-5$ are all contained in the image of $f$.

Setting $f(y)=-2$, we have $f(x+2)=f(x)^2+f(2x+2)\equiv f(x) \mod \,2$.

Setting $f(y)=-1$, we have $f(x+1)=f(x)^2+f(2x+1)$. Setting $x+2$ in the place of $x, \,f(x+3)=f(x+2)^2+f(2x+5)$.

Setting $f(y)=-5$, we have $f(x+5)=f(x)^2+f(2x+5)$.

Subtracting the two equations above, we get

$\displaystyle f(x+3)-f(x+5)=f(x+2)^2 - f(x)^2 \ \ \ \ \ \ \ \ \ \ \ \ (*)$

(This is why we used $x+2$ instead of $x$ when $f(y)=-1$, as that would permit us to subtract and reduce one term.)

Upto this point, we haven’t used any property of $\mathbb Z$ (we haven’t in fact used the parity condition). But in an Olympiad problem, we should aim to use all the given conditions, as the problems are almost always tailored such that the conditions just suffice for a solution using elementary method. Now we observe that the LHS of the equation (*) is the difference between two terms with distance $2$ apart, while the RHS has a factor that is also a difference between two terms with distance $2$ apart, with another factor whose absolute value is at least $1$ if we can make sure it is not zero. We want it to be $1$. This can be done by inequality.

If $\forall x \in \mathbb Z, f(x+2)-f(x)=0$, then $f$ is a constant on even number (with that value being thus $0$ as $f(0)=0$) and a constant on odd number (with that value thus being $-1$ as otherwise $-1$ would not be in the range of $f$.) Now, we have shown that $-2$ is also in the image of the function, thus this is a contradiction.

Thus $\exists x\in \mathbb Z, f(x+2)-f(x)\ne 0$. Consider the set $\{\left \vert f(x+2)-f(x)\right \vert \, | \, f(x+2)-f(x)\ne 0\}$, with its minimal element being attained at $x=\sigma$. Substitute $x=\sigma -3$ into (*), and take absolute value.

$|f(\sigma+2)-f(\sigma)|=|f(\sigma -1)-f(\sigma -3)| |f(\sigma -1)+f(\sigma -3)|$.

By the minimality condition, $\lvert f(\sigma -1)-f(\sigma -3)\rvert \ge \lvert f(\sigma+2)-f(\sigma)\rvert$, and $\lvert f(\sigma -1)+f(\sigma -3)\rvert\ge 1$ because it does not vanish (as the LHS is non-zero)

Multiplying them, we have equality in the face of two inequalities. Thus the two inequalities must have equality holding at the same time, thus $f(\sigma-1)-f(\sigma -3) =\pm 1$ . This is impossible since we have shown above that $f(x) \equiv f(x+2)\mod 2,\forall x\in \mathbb Z.$

Q.E.D.

Comment: The problem is not very difficult, and many alternative methods exist, as the function itself is quite bizarre and repeated substitution per se gives more and more information from which any contradiction would finish the problem off.

The problem is proposed by Qiang Shen, and used in a practice exam at Renhui Jiuzhang MO Tuition Centre (Beijing, China) in 2015.

Standard