## IMO 1996 Day 1

**Problem 1** We are given a positive integer and a rectangular board with dimensions . The rectangle is divided into a grid of 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 . The task is to find a sequence of moves leading from the square with as a vertex to the square with as a vertex.

(a) Show that the task cannot be done if is divisible by or .

(b) Prove that the task is possible when .

(c) Can the task be done when ?

**Solution:** First note that a move from the square to the square if and only if .

(a) If is divisible by then the steps have so is invariant. Therefore we cannot go from to .

If is divisible by then again for any step we have so is invariant. It is obvious then that we cannot go from to .

(b) If we can make only steps of the form , and after a quick search we can find a solution (note that the minimal number of steps is ). Here it is: .

(c) The answer is no. For we can take only steps of the form . Note that we can get right away from to in two steps. Now let’s show that you cannot go from a little square to an adjacent one horizontally.

Divide the grid into three horizontal strips of width . 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 vertically you end up in the middle strip on an even column. If you make a jump of 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 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 to in this case.

Note that this generalizes to every situation of the form where .

**Problem 2** Let be a point inside a triangle such that

Let , be the incenters of triangles , , respectively. Show that the lines , , meet at a point.

**Solution:** I will give first my solution and then hints to other solutions. Construct such that is similar to . As a consequence you also get that is similar to . The angle condition translates to and writing the ratios from the similarity of the two pairs of triangles we get

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

Here are some other ideas I saw:

- Idea 1 Make an inversion about . You will get something similar to my solution.
- Idea 2 Reflect over .
- Idea 3 Consider the intersection of with and the circumcircle of and work with area ratios.
- Idea 4 Apollonius circle.

**Problem 3** Let denote the set of nonnegative integers. Find all functions from to itself such that

**Solution:** Choose and get and . First note that the zero function and the identity are solutions. Secondly, if is the image of then we easily see that (Minkowski sum). It’s an easy argument from here to see that if is the smallest non-zero element of and then divides all the elements from . Furthermore, we have for every . From this last relation and the remark above we see that this relation determines uniquely the function given arbitrary multiples of .

Reblogged this on MatheMazier.