INMO 2015

We have to prove that $f: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ defined by

is a bijection. (Note that the right side is a natural number.) To this end define

An idea of the proof can be obtained by looking at the following table of values of $f(a, b)$ for some small values of $a, b$. We observe that the $n$-th diagonal runs from $(1, n)$-th position to $(n, 1)$-th position and the entries are $n$ consecutive integers; the first entry in the $n$-th diagonal is one more than the last entry of the $(n-1)$-th diagonal. For example the first entry in 5-th diagonal is 11 which is one more than the last entry of 4-th diagonal which is 10. Observe that 5-th diagonal starts from 11 and ends with 15 which accounts for 5 consecutive natural numbers. Thus we see that $f(n-1, 1) + 1 = f(1, n)$. We also observe that the first $n$ diagonals exhaust all the natural numbers from 1 to $T(n)$. (Thus a kind of visual bijection is already there. We formally prove the property.)

We first observe that

and

Thus we have

Suppose $f(a_1, b_1) = f(a_2, b_2)$. Then the previous observation shows that

Since the sequence $\langle T(n) \rangle_{n=0}^{\infty}$ is strictly increasing, it follows that $a_1 + b_1 = a_2 + b_2$. But then the relation $f(a_1, b_1) = f(a_2, b_2)$ implies that $a_1 = a_2$ and $b_1 = b_2$. Hence $f$ is one-one.

Let $n$ be any natural number. Since the sequence $\langle T(n) \rangle_{n=0}^{\infty}$ is strictly increasing, we can find a natural number $k$ such that

Equivalently,

Now set $a = n - \frac{k(k-1)}{2}$ and $b = k - a + 1$. Observe that $a > 0$. Now (1) shows that

Hence $b = k - a + 1 \geq 1$. Thus $a$ and $b$ are both positive integers and

This shows that every natural number is in the range of $f$. Thus $f$ is also onto. We conclude that $f$ is a bijection.

We show that the solution set consists of $\{(t, 0, 0) ; t \in \mathbb{Z}\} \cup \{(-1, -1, 1)\}$. Let us put $a + b + c = d$, $ab + bc + ca = e$ and $abc = f$. The given condition $f(f(a, b, c)) = (a, b, c)$ implies that

Thus $abcdef = fc$ and hence either $cf = 0$ or $abde = 1$.

Case I: Suppose $cf = 0$. Then either $c = 0$ or $f = 0$. However $c = 0$ implies $f = 0$ and vice-versa. Thus we obtain $a + b = d$, $d + e = a$, $ab = e$ and $de = b$. The first two relations give $b = -e$. Thus $e = ab = -ae$ and $de = b = -e$. We get either $e = 0$ or $a = d = -1$. If $e = 0$, then $b = 0$ and $a = d = t$, say. We get the triple $(a, b, c) = (t, 0, 0)$, where $t \in \mathbb{Z}$. If $e \neq 0$, then $a = d = -1$. But then $d + e + f = a$ implies that $-1 + e + 0 = -1$ forcing $e = 0$. Thus we get the solution family $(a, b, c) = (t, 0, 0)$, where $t \in \mathbb{Z}$.

Case II: Suppose $cf \neq 0$. In this case $abde = 1$. Hence either all are equal to $1$; or two equal to $1$ and the other two equal to $-1$; or all equal to $-1$. Suppose $a = b = d = e = 1$. Then $a + b + c = d$ shows that $c = -1$. Similarly $f = -1$. Hence $e = ab + bc + ca = 1 - 1 - 1 = -1$ contradicting $e = 1$. Suppose $a = b = 1$ and $d = e = -1$. Then $a + b + c = d$ gives $c = -3$ and $d + e + f = a$ gives $f = 3$. But then $f = abc = 1 \cdot 1 \cdot (-3) = -3$, a contradiction. Similarly $a = b = -1$ and $d = e = 1$ is not possible. If $a = 1, b = -1, d = 1, e = -1$, then $a + b + c = d$ gives $c = 1$. Similarly $f = 1$. But then $f = abc = 1 \cdot 1 \cdot (-1) = -1$ a contradiction. If $a = 1, b = -1, d = -1, e = 1$, then $c = -1$ and $e = ab + bc + ca = -1 + 1 - 1 = -1$ and a contradiction to $e = 1$. The symmetry between $(a, b, c)$ and $(d, e, f)$ shows that $a = -1, b = 1, d = 1, e = -1$ is not possible. Finally if $a = -1, b = 1, d = -1$ and $e = 1$, then $c = -1$ and $f = -1$. But then $f = abc$ is not satisfied. The only case left is that of $a, b, d, e$ being all equal to $-1$. Then $c = 1$ and $f = 1$. It is easy to check that $(-1, -1, 1)$ is indeed a solution.

Alternatively $cf \neq 0$ implies that $|c| \geq 1$ and $|f| \geq 1$. Observe that

Adding these two, we get $-2(b + e) = b^{2} + c^{2} + e^{2} + f^{2}$. This may be written in the form

We conclude that $c^{2} + f^{2} \leq 2$. Using $|c| \geq 1$ and $|f| \geq 1$, we obtain $|c| = 1$ and $|f| = 1$, $b + 1 = 0$ and $e + 1 = 0$. Thus $b = e = -1$. Now $a + d = d + e + f + a + b + c$ and this gives $b + c + e + f = 0$. It follows that $c = f = 1$ and finally $a = d = -1$.

Applying cosine rule to triangle $ABC$, we get

Observe that $\angle DAC = \angle DBC = 120^\circ - 30^\circ = 90^\circ$. Thus we get

So

This proves $c \geq a + b$ and thus (i) is true.

For proving (ii), consider the product

where $\alpha = \sqrt{c+a}$, $\beta = \sqrt{c+b}$ and $\gamma = \sqrt{c-a-b}$. Expanding the product, we get

Thus at least one of the factors must be equal to $0$. Since $\alpha + \beta + \gamma > 0$ and $\alpha + \beta - \gamma > 0$, it follows that the product of the remaining two factors is $0$. This gives

We conclude that

a. Let $n \geq 4011^{2}$ and $m \in \mathbb{N}$ be such that $m^{2} \leq n < (m+1)^{2}$. Then

Thus we get

and $l^{2} = (m+1)^{2}$ is the desired square.

b. We show that $M = 4010^{2} + 1$ is the required least number. Suppose $n \geq M$. Write $n = 4010^{2} + k$, where $k$ is a positive integer. Note that we may assume $n < 4011^{2}$ by part (a). Now

Thus we obtain

We check that $M = 4010^{2}$ will not work. For suppose $n = 4010^{2}$. Then

Thus there is no square integer between $n$ and $\left(1 + \frac{1}{2005}\right) n$. This proves (b).

Solution 1.

Since $E$ is the mid-point of $AC$, we have $AE = EC = b/2$. Since $BD$ bisects $\angle ABC$, we also know that $CD = ab/(a+c)$. Since $BE$ bisects $\angle ABD$, we also have

However,

Using these in the above expression and simplifying, we get

Using $c^{2}=a^{2}+b^{2}$ and eliminating $b$, we obtain

Introducing $t=c/a$, this reduces to a cubic equation;

Consider the function $f(t)=t^{3}-2t^{2}-t-2$ for $t>0$ (as $c/a$ is positive). For $0<t \leq 2$, we see that $f(t)=t^{2}(t-2)-t-2<0$. We also observe that $f(t)=(t-2)(t^{2}-1)-4$ is strictly increasing on $(2, \infty)$. It is easy to compute

Hence there is a unique value of $t$ in the interval $(5/2,3)$ such that $f(t)=0$. We conclude that

Solution 2.

Let us take $\angle B/4=\theta$. Then $\angle EBC=\angle DBE=\theta$ and $\angle CBD=2\theta$. Using sine rule in triangles $BEA$ and $BEC$, we get

Since $AE=CE$, we obtain $\sin 3\theta \sin A=\sin \theta$. However $A=90^{\circ}-4\theta$. Thus we get $\sin 3\theta \cos 4\theta=\sin \theta$. Note that

This shows that $c/a<3$. Using $c/a=3-4\sin^{2}\theta$, it is easy to compute $\cos 2\theta=((c/a)-1)/2$. Hence

Suppose $c/a \leq 5/2$. Then $((c/a)-1)^{2} \leq 9/4$ and $a/c \geq 2/5$. Thus

which is absurd. We conclude that $c/a>5/2$.

It can be easily seen that

Thus we can take $p_{1} = p_{2} = p_{3} = 2$, $q_{1} = q_{2} = q_{3} = 2$ and $r_{1} = r_{2} = r_{3} = -1$. Suppose $3$ does not divide $\gcd(a, b, c)$. Then $3$ does divide at least one of $a, b, c$; say $3$ does not divide $a$. Note that each of $2 b + 2 c - a$, $2 c + 2 a - b$ and $2 a + 2 b - c$ is either divisible by $3$ or none of them is divisible by $3$, as the difference of any two sums is always divisible by $3$. If $3$ does not divide $2 b + 2 c - a$, then we have the required representation. If $3$ divides $2 b + 2 c - a$, then $3$ does not divide $2 b + 2 c + a$. On the other hand, we also note that

where $x = 2 b + 2 c + a$, $y = 2 c - 2 a - b$ and $z = -2 a + 2 b - c$. Since $x - y = 3(b + a)$ and $3$ does not divide $x$, it follows that $3$ does not divide $y$ as well. Similarly, we conclude that $3$ does not divide $z$.