IMO 2016 was held from 6/7/2016 to 16/07/2016. Although I didn’t attend this, I just want to post my solutions and how I think about the difficulty of the problems, which can be found here. I will post my solutions on this post. Many awesome solutions can be found on AoPS.
Problem 2. Find all integers for which each cell of table can be filled with one of the letters and in such a way that:
- in each row and each column, one third of the entries are , one third are and one third are ; and
- in any diagonal, if the number of entries on the diagonal is a multiple of three, then one third of the entries are , one third are and one third are .
Note. The rows and columns of an table are each labelled to in a natural order. Thus each cell corresponds to a pair of positive integer with . For , the table has diagonals of two types. A diagonal of first type consists all cells for which is a constant, and the diagonal of this second type consists all cells for which is constant.
Solution. Here is a solution using counting in two ways. The answer is all .
It’s obvious that . We consider all the squares indexed and call it good square. Let be number of good squares that are filled with . We can see that every good square lies on both type of diagonals. So if we call be the set of all squares in first type, second type of diagonal that are filled with , respectively. We will have and . Hence,
Hence, number of squares filled with that either lie on first type of diagonal or second type is .
Now, these squares counted above doesn’t fill the columns indexed and rows indexed . So we need to fill these squares with . Let be the set of squares in columns indexed that are filled with , similar to set of rows indexed . We have
From these, we find that the total number of squares filled with is . Note that this is also equal to so this means implies , which is the final answer.
This argument gives us a way to construct a table, which is first we fill all the good squares in a way such that one third of them are , one third are and one third are . After that, we fill all the diagonals and then fill the remain squares.
A very simple construction for square of Evan Chen can be found in AoPS forum (link provided above). We can see that this is a direct counting problem, with a main notice is that if we exclude all diagonals (both types) then the remaining squares can only lie on either rows indexed or columns indexed . I think I’ve seen this type of problem before (board problem and use direct counting), I will try to search if I can find it. This problem took me a whole night to solve.
Problem 3. Let be a convex polygon in the plane. The vertices have integral coordinates and lie on a circle. Let be the area of . An odd positive integer is given such that the squares of the side lengths of are integers divisible by . Prove that is an integer divisible by .
Solution. Yes, induction on works.
For then it’s obviously true according to Heron’s formula.
If it’s true till convex polygon with vertices, we need to prove that it’s also true for convex polygon with vertices. Indeed, we will show that there exists a diagonal such that for odd prime divisor of . Assume contradiction, that means for all and . Now, according to Ptolemy’s theorem for any four vertices (denote as the length of side ) with we have
Therefore . From the contradict assumption, we have
and so that means
Since this equality is true for all so we add all up and get a contradiction.
This means there will exists such that . We divide the big polygon in to two smaller polygons with areas by the diagonal . From the inductive hypothesis, we have , which follows . Thus, we obtain .
This is the strangest problem in the competition and also the most beautiful problem. It combines between number theory and geometry. I think what makes this problem hard to solve during the competition is because of it is unfamiliar, that’s all. If you read the solution above, you can see that the idea process is very familiar in olympiad number theory: induction + prove mod p to obtain mod n. The rest is just mainly comparing using some knowledge in geometry (in above I used Ptolemy’s theorem, there are many other ways, like using Inversion – Jeck Lim’s solution on AoPS). This problem took me 2 days to solve, mainly because I was too focus on some stupid calculation of sides of polygons. I should’ve thought of induction sooner.
Updated: silouan (AoPS) found a very similar problem to problem 3, use the same method to solve:
[IMO Shortlist 2004, N7] Let be an odd prime and a positive integer. In the coordinate plane, eight distinct points with integer coordinates lie on a circle with diameter of length . Prove that there exists a triangle with vertices at three of the given points such that the squares of its side lengths are integers divisible by .
Problem 6. There are line segments in the plane such that every two segments cross and no three segments meet at a point. Geoff has to choose an endpoint of each segment and place a frog on it facing the other endpoint. Then he will clap his hands times. Every time he claps,each frog will immediately jump forward to the next intersection point on its segment. Frogs never change the direction of their jumps. Geoff wishes to place the frogs in such a way that no two of them will every occupy the same intersection point at the same time.
(a) Prove that Geoff can always fulfil his wish if is odd.
(b) Prove that Geoff can never fulfil his wish if is even.
I can only solve 6(a): choose a line and place a frog on a line anywhere. For all other lines ,
– if frog on passes on even clap, place frog on such that it passes on odd clap.
– vice versa.
Choose any two lines and and a simple geometry argument shows that two frogs pass in claps of different parity, which means the frogs cannot occupy the same intersection at the same time.
My construction for a) is the same as qwerty414’s post in #4. From this one, it suffices to prove that for any two lines , they can’t occupy the same intersection point at the same time.
Let be , be and be and the frogs start with . Assume contradiction that occupy the same intersection point at the same time. Hence, number of jumps from to must have same parity with number of jumps from to .
A note that from the construction, number of jump from to must have different parity with number of jumps from to , similarly to to and to . From these, in all cases, we must have either number of jumps from to , to , to are all even or one of these three are even, the remain two are odd. Thus, if the call be number of points between and , and , and then we always have .
On the other hand, since if a line passes through then it can’t cut , vice versa. So that means there exists such that where be number of points that pass through , similarly to . Thus, , a contradiction.
Therefore, can’t occupy the same intersection at the same time. Thus, for odd, Geoff always fulfil his wish.
My idea to solve (a) doesn’t work with (b). Actually, all (a) and (b) can be solved using a trick: drawing a circle containing all the intersections of lines. This idea, which can be viewed on AoPS, make it very easy for anyone who knows (that’s why many people – not me – said IMO this year has the easiest problem 6). This idea came cross my mind once but I can’t notice the main point why we should do that, so I failed to apply it. Instead, I found a different approach for (a). I think there is some problems using this trick before. Anyway, part (a) took me 7-8 hours to solve (I try to attempt for few hours and fell hopeless so I went to sleep, and after I wake up, I find this idea). An open question is that what if instead of lines, the frogs go in a polygon way?
Problem 4. A set of postive integers is called fragrant if it contains at least two elements and each of its elements has a prime factor in common with at least one of the other elements. Let . What is the least possible positive integer value of such that there exists a non-negative integer for which the set
Solution. Consider and . We note that in order to and we must have and . It is obvious that since or .
If then implies . WLOG, we can let and see that . So there doesn’t exists so that .
If , we find and we let . Hence, from we get . So there is one prime such that .
If , it is obvious that satisfy and is the only answer.
If , we do the similar thing and get and so .
Now, back to the problem, since there doesn’t exists any prime for so . The only prime for is so if we choose then there will be a number remains. This means since we need a prime and but since .
If , we consider two cases, where there are two numbers that are divisible by (which means ), the middle-three numbers we can’t find a way make each two of them have common prime factor. If no two are divisible by then they can only be divisible by , but it can’t cover all “consecutive” numbers.
If then we can pick .
So the final answer is .
I was spoiled by the answer for this problem, took me 40 min to solve. However, I still think this problem is not hard. It applies classic number theory idea (CRT, gcd, mod prime). I see that this problem is just a small case, so the open question is if the property of fragrant set change to: “each of its elements has a prime factor in common with at least of the other elements” or maybe “each of its elements has at least two prime factors in common with at least one of the other elements” then what will be the best bound for ?
Problem 5. The equation
is written on the board, with linear factors on each side. What is the least possible value of for which it is possible to erase exactly of these linear factors so that at least one factor remains on each side and the resulting equation has no real solutions?
Updated: I found a problem that looks like problem 5:
[Australia MO 2015] Determine the number of distinct real solutions of the equation
I was spoiled to much (on AoPS) in problem 5 so I just read the solution on AoPS anyway. I solved problem 1 (geometry problem) but after seeing more than 50 posts in here, I lost my motivation in posting my solution. It is a nice figure though, but the problem is stated with too many points. Problem 1 took me about an hour and a half to solve. Again, I think I can solve this less than an hour but I was too focus on stupid calculation of sides instead of trying to find new properties of figure sooner.
In difficult orders, I would say . Many people would order problem as easy problem, but for me, it’s a hard one, harder than (in how to think of that idea). Although I didn’t attempt problem , but I think it would be around same level with problem (hopefully).
In quantity orders, I think . Yes, problem is the most beautiful one, no doubt about that. I don’t have any other comments about other problems.
Basically, IMO2016 has many interesting problems (3,5,6). I think it would be nicer if the judge could replace problem 4 by a geometry problem.