Some problems from Indian National Mathematics Olympiad, 2014

I just want to add a couple of problems from INMO 2014 that I solved this morning. The first problem was slightly less tricky, and just involved pairing divisors with each other in the most obvious way. However, the second problem is quite devious, and is more of an existence proof than writing down an explicit winning strategy.

Let $n$ be a natural number. Prove that $\left\lfloor \frac{n}{1} \right\rfloor+\left\lfloor \frac{n}{2} \right\rfloor+\dots+\left\lfloor \frac{n}{n} \right\rfloor+\left\lfloor \sqrt{n} \right\rfloor$ is even.

We will prove this by induction. Let $f(n)=\left\lfloor \frac{n}{1} \right\rfloor+\left\lfloor \frac{n}{2} \right\rfloor+\dots+\left\lfloor \frac{n}{n} \right\rfloor+\left\lfloor \sqrt{n} \right\rfloor$ . Note that $f(1)=2$ is even. Also, note that $f(i)=f(i+1)+$ the number of divisors of $i+1$ . It is precisely at those divisors that $1$ is added to $f(i+1)$ . If $i+1$ is not a square, then the number of divisors can be paired up as $(d,\frac{i+1}{d})$ . Hence, the number of divisors should be even. Moreover, $\lfloor \sqrt{i}\rfloor=\lfloor \sqrt{i+1}\rfloor$ . However, if $i+1$ is indeed a square, then $\sqrt{i+1}$ is a divisor that cannot be paired up with a different divisor as $\frac{i+1}{\sqrt{i+1}}=\sqrt{i+1}$ itself. However, $\lfloor \sqrt{i+1}\rfloor=\lfloor \sqrt{i}\rfloor+1$ . Hence, we get two extra 1’s, which still keeps $f(i+1)$ even. Hence, $f(i)$ and $f(i+1)$ have the same parity. Now as $f(1)=2$ is even, $f(i)$ is even for all $i\geq 1$ . Hence proved. QED

Written on a blackboard is the polynomial $x^2+x+2014$ . Calvin and Hobbes take turns alternately (starting with Calvin) in the following game. During his turn, Calvin should either increase or decrease the coefficient of $x$ by $1$ . And during his turn, Hobbes should either increase or decrease the constant coefficient by $1$ . Calvin wins if at any point of time the polynomial on the blackboard has integer roots. Prove that Calvin has a winning strategy.

Calvin’s first move should be to increase the coefficient of $x$ by $1$ . We will prove that Calvin has a winning strategy by induction.

Observe that for $x^2+x+2$ , Calvin has the following winning strategy: After the first move, the polynomial becomes $x^2+2x+2$ . Now if Hobbes keeps increasing the constant coefficient, Calvin should do the same. If Hobbes reduces the constant coefficient at any step, the polynomial will becomes $x^2+ax+(a-1)=0$ , which has the integer roots $1,a-1$ . Hence, Calvin has a winning strategy for $x^2+x+2k$ when $k=1$ .

Note that for the general polynomial $x^2+x+2k$ , if both players keep increasing the coefficients without ever decreasing them, ultimately the polynomial becomes $x^2+(1+k+3)x+(2k+k+3)=0$ , which has the integer roots $3,k+1$ . Hence, in order to avoid losing, Hobbes should reduce the constant coefficient at least once.

We will use a form of strong induction here. If Calvin has a winning strategy for $x^2+x+2k$ , then he has a winning strategy for any $x^2+(1+a)x+(2k+a)=0$ , where $a\leq k+3$ .

Let us assume that Calvin has a winning strategy for $x^2+x+2k$ . From the last statement, we know that this implies that Calvin has a winning strategy for $x^2+(1+a)x+(2k+a)=0$ , where $a\leq k+3$ . Now let us consider $x^2+x+2(k+1)=0$ . If Hobbes keeps increasing the constant coefficient, then we know that Calvin should do the same, and that is a winning strategy. If after $a$ moves, where $a<k+1+3$ , if Hobbes decreases the constant coefficient on the $(a+1)$ th move, then the polynomial becomes $x^2+(1+a+1)x+(2k+2+a-1)=x^2+(1+a+1)+(2k+a+1)=0$ . By strong induction, we know that Calvin has a winning strategy for this. Hence proved. QED.