## IMO 1996 Day 1

Problem 1 We are given a positive integer ${ r}$ and a rectangular board ${ ABCD}$ with dimensions ${ AB = 20, BC = 12}$. The rectangle is divided into a grid of ${ 20 \times 12}$ unit squares. The following moves are permitted on the board: one can move from one square to another only if the distance between the centers of the two squares is ${ \sqrt {r}}$. The task is to find a sequence of moves leading from the square with ${ A}$ as a vertex to the square with ${ B}$ as a vertex.

(a) Show that the task cannot be done if ${ r}$ is divisible by $2$ or $3$.

(b) Prove that the task is possible when ${ r = 73}$.

(c) Can the task be done when ${ r = 97}$?

Solution: First note that a move from the square ${(a,b)}$ to the square ${(c,d)}$ if and only if ${(a-c)^2+(b-d)^2=r}$.

(a) If ${r}$ is divisible by ${2}$ then the steps ${(x,y)}$ have ${x\equiv y\mod 2}$ so ${x-y \mod 2}$ is invariant. Therefore we cannot go from ${(1,1)}$ to ${(20,1)}$.

If ${r}$ is divisible by ${3}$ then again for any step ${(x,y)}$ we have ${3 |x,\ 3|y}$ so ${x-y\mod 3}$ is invariant. It is obvious then that we cannot go from ${(1,1)}$ to ${(20,1)}$.

(b) If ${r=73}$ we can make only steps of the form ${(\pm 3,\pm 8)}$, and after a quick search we can find a solution (note that the minimal number of steps is ${11}$). Here it is: ${(1,1)\rightarrow (4,9) \rightarrow (12,6) \rightarrow (4,3)\rightarrow (7,11)\rightarrow (15,8)\rightarrow (7,5)\rightarrow (15,2)\rightarrow (12,10) \rightarrow (20,7) \rightarrow (12,4) \rightarrow (20,1)}$.

(c) The answer is no. For ${r=97}$ we can take only steps of the form ${(\pm 4,\pm 9)}$. Note that we can get right away from ${(1,1)}$ to ${(19,1)}$ in two steps. Now let’s show that you cannot go from a little square to an adjacent one horizontally.

Divide the ${20\times 12}$ grid into three horizontal strips of width ${4}$. Suppose we are (like in our case) on an odd column in the lower strip. Where can we go now? Note that every move takes you to another strip. If you make a jump of ${4}$ vertically you end up in the middle strip on an even column. If you make a jump of ${9}$ vertically you arrive in the upper strip on an odd column. From the middle strip, where we are on an even column we can only make vertical jumps of length ${4}$ which land in one of the upper or lower strip on an odd column. From the upper strip we can arrive in the middle strip on an even column or in the first strip on an odd column. So the invariant of the movements is the fact that in the upper and lower strip we can reach only odd columns and in the middle strip only even columns. Therefore we cannot go from ${(1,1)}$ to ${(20,1)}$ in this case.

Note that this generalizes to every situation of the form ${(d,2d+1)}$ where ${d | 12}$.

Problem 2 Let ${ P}$ be a point inside a triangle ${ ABC}$ such that

$\displaystyle \angle APB - \angle ACB = \angle APC - \angle ABC.$

Let ${ D}$, ${ E}$ be the incenters of triangles ${ APB}$, ${ APC}$, respectively. Show that the lines ${ AP}$, ${ BD}$, ${ CE}$ meet at a point.

Solution: I will give first my solution and then hints to other solutions. Construct ${Y}$ such that ${\Delta APB}$ is similar to ${\Delta ACY}$. As a consequence you also get that ${\Delta ABY}$ is similar to ${\Delta APC}$. The angle condition translates to ${BY=CY}$ and writing the ratios from the similarity of the two pairs of triangles we get

$\displaystyle \frac{AB}{BP}=\frac{AC}{PC},$

which is easily seen to be equivalent to the desired concurrency.

Here are some other ideas I saw:

• Idea 1 Make an inversion about ${A}$. You will get something similar to my solution.
• Idea 2 Reflect ${BC}$ over ${BD,BE}$.
• Idea 3 Consider the intersection of ${AP}$ with ${BC}$ and the circumcircle of ${ABC}$ and work with area ratios.
• Idea 4 Apollonius circle.

Problem 3 Let ${ \mathbb{N}_0}$ denote the set of nonnegative integers. Find all functions ${ f}$ from ${ \mathbb{N}_0}$ to itself such that

$\displaystyle f(m +f(n)) = f(f(m)) + f(n)\qquad \text{for all} \; m, n \in \mathbb{N}_0.$

Solution: Choose ${m=n=0}$ and get ${f(0)=0}$ and ${f(f(m))=f(m),\ \forall m \in \Bbb{N}_0}$. First note that the zero function and the identity are solutions. Secondly, if ${A=f(\Bbb{N}_0)}$ is the image of ${f}$ then we easily see that ${A=A+A}$ (Minkowski sum). It’s an easy argument from here to see that if ${r}$ is the smallest non-zero element of ${A}$ and ${r \geq 2}$ then ${r}$ divides all the elements from ${A}$. Furthermore, we have ${f(m+r)=f(m)+r}$ for every ${m \in \Bbb{N}_0}$. From this last relation and the remark above we see that this relation determines uniquely the function ${f}$ given ${f(1),..,f(r-1)}$ arbitrary multiples of ${r}$.