The 41^st IMO 
(official site : The 41st International Mathematical Olympiad )

Problems

Day one

1. Two circles G₁ and G₂ intersect at M and N. Let l be the common tangent to G₁ and G₂ so that M is closer to l than N is. Let l touch G₁ at A and G₂ at B. Let the line through M parallel to l meet the circle G₁ again at C and the circle G₂ again at D. Lines CA and DB meet at E; lines AN and CD meet at P; lines BN and CD meet at Q. Show that EP=EQ.

2. Let a,b,c be positive real numbers such that abc=1. Prove that :

3. Let n ³ 2 be a positive integer. Initially, there are n fleas on a horizontal line, not all at the same point. For a positive l define a move as follows: choose any two fleas at points A and B with A to the left of B; let the flea at A jump to the point C to the left of B with BC/AB=l.
Determine all values of l such that, for any point M on the line and any initial positions of the n fleas, there is a finite sequence of moves that will take all fleas to positions to the right of M.

4. A magician has one hundred cards numbered 1 to 100. He puts them into three boxes, a red one, a white one and a blue one, so that each box contains at least one card. A member of the audience selects two of the three boxes, chooses one card from each and announces the sum of the numbers on the chosen cards. Given this sum, the magician identifies the box from which no card has been chosen. How many ways are there to put all the cards into the boxes so that this trick always works? (two ways are different if at least one card is put in a different box)

5. Determine whether or not there exists a positive integer n such that n is divisible by exactly 2000 different prime numbers, and 2ⁿ+1 is divisible by n.

6. Let AH₁, BH₂, CH₃ be the altitudes of an acute angled triangle ABC. The incircle of the triangle ABC touches the sides BC, CA, AB at T₁ , T₂, T₃ respectively. Let the lines l₁, l₂, l₃ be the reflections of H₂H₃ , H₃H₁ , H₁H₂ in the lines T₂T₃ , T₃T₁ , T₁T₂.
Prove that the lines l₁, l₂, l₃ determine a triangle whose vertices lie on the incircle of the triangle ABC.

1. It is elementary to prove, using angles, that the triangles ACM and MBD are isosceles. Using CM=2CAcos ACN and the analogous relation, since CD=CN+ND we get that A is the midpoint of CE and B is the midpoint of ED. This in turn yields that M is the foot of the altitude from E in the triangle ECD. If S is the intersection of MN with AB the S is on the radical axis of the two circles which means that SA=SB. Using the theorem of Thales we have MP/SA=NM/NS=MP/SB which means PM=QM. Since EM is perpendicular on CD we get EP=EQ.

2. Substitute a=x/y, b=y/z and c=z/x and the inequality becomes (-x+y+z)(x-y+z)(x+y-z)£xyz. If -x+y+z=u, x-y+z=v and x+y-z=w then we have to prove (u+v)(v+w)(w+u)³8uvw and this is easy using the AM-GM inequality for positive u,v,w and just analysing it for negative ones too.

3. Chose O a point to the left of all fleas. Jump the first flea over the last one. If a_m is the distance from O to the flea on the n th position then we have the recurring formula: a_m+1 = a_m + l(a_m - a_m-n ). This has the characteristic equation : xⁿ⁺¹ - (l+1)xⁿ +l = 0. This equation already has a root equal to 1. If n is even then it has exactly three real roots. Otherwise it has one real root and the others are complex. Since the formula for the general term of the sequence is a sum of powers, and because the sequence in discussion deffinitely must be increasing, then there must be a root of modulus at least 1. (if 1 then since there are at least two 1 roots the general term will contain a polynomial of degree at least 1). This would have a positive coeficient and would be unbounded. This means that for l = (xⁿ⁺¹ - xⁿ)/(xⁿ - 1) = 1/(1/x + 1/x² +...+1/x^n-1)³1/(n-1).
If l<1/(n-1) then take S be the sum from O to all the fleas at one time. Given a set of n fleas and a random jump from coordinate a over the coordinate b.(coordinates with respect to O) let the first one be at c and the last one be at d. In the first case S increases with (1+l)(b-a). In the last case it increases with (1+l)(d-c) which is clearly greater. Given two sets of fleas U=(a,b,...,z) and V=(a',b',...,z') then UÐV if and only if  z-a£z'-a'. In this case S(U)£S(V). Taking a random jump in U and the maximal jump in V (that is the jump of the first over the last flea). Clearly S(U) increases with less than (l+1)(z-a)£(l+1)(z'-a') which is the amount by which S(V) increases. And furthermore the distance from the first to the last flea in U after the jump is still less than the corresponding difference in V after the jump. This means that if U'and V'are the tranformed sets of U and V respectively then U'ÐV'. Thus by taking a sequence of random moves of a given set P of n fleas : P, P', P'',... and a sequence of maximal moves starting with P: Q=P, Q', Q''... then inductively P^(k)ÐQ^(k) which means that S(P^(k)) is less or equal to S(Q^(k)). If l<1/(n-1) then all the roots of the characteristic equation have modulus less than 1 and therefore the sequence a_m is bounded. Then S(P^(k))£S(Q^(k))£na_k+n which is obviously bounded. Assuming that the sequence of random moves P,P',... takes a flea beyond M for any M this means that S(P^(k)) should be unbounded. This is a contradiction. Thus the sought values for l are l³1/(n-1).

4. We shall prove by induction that the only possible divisions of the cards are the residue classes modulo 3 and the sets {1}, {2...n-1} and {n} for cards from 1 to n. The problem os equivalent to the following: determine the partitions of 1...n into the sets A,B and C so that A+B,B+C and C+A have no element in common. For n=3 then the only partition is {1}{2}{3}which verifies both possible partitions. Assume the problem solved for n-1 and proceed to n. Exactly one of the sets A,B and C say C contains the element n. Assume that none of the sets A,B and C consists only of the element n. Then eliminate n from C and obtain D. Clearly A+B,B+D and D+A are disjoint since A+B,B+C and C+A are disjoint. Then because the sets A,B and D are not empty apply the inductive hypothesis and thus A,B and D are either the residue classes mod 3 or are {1} {2...n-2}{n-1}. If D is {1} then take A the second and B the last set. A+C and A+B have n+2 in common. If D is {n-1}let A be the first and B the last set. A+C and B+C have n+1 in common. If D is {2,...,n-2} let A={1} and B={n-1}. Then A+C and B+C have n+1 in common. Thus A,B and D are the residue classes mod 3. This clearly yields a contradiction.
Assume C={n}. Then A={a_i} and B={b_i} and a_i+n and b_i+n are different which is obvious, and a_i+b_j and n+a_k are different as well as the analogous relation. Let A have a and B have b elements. Clearly A+C has n elements and B+C has b elements. It is known (and easy to prove) that A+B has at least a+b-1 elements. Since all sums of two are disjoint and since X+Y is in the set 3...2n-1 where X and Y are different sets in the set {A,B,C}.Then 2n-3 is greater or equal to the sum of cardinalities of X+Y. Thus a+b+a+b-1 is less or equal to 2n-3. But a+b=n-1 thus 2n-3 less or equal to 2n-3 and equality is attained. Thus cardA+B=cardA + cardB which happens only if A and B either one has one element (in which case this must necesarily be {1}) or they are arithmetical progressions of equal common difference. This comes easily from the condition imposed on A+B (this must consist only of the sums of A with the least of B and the sums of B with the greatest of A) If they are progressions with equal differences then : let 1 be in A and b the least element of B. If b>2 then clearly n-1 is in A since otherwise A+B and A+C are not disjoint. Thus A has common difference 1 and has 1 and n-1. Thus B is empty. Thus 2 is in B. If 3 is in B then a similar contradiction appears. Thus 3 is in A and therefore A has all the odd and B all the even numbers. But this is obviously not a valid partition. The induction is therefore complete.

5. Let M be the set of all n so that n divides 2ⁿ+1. It is easy that 3^k is in M. Let a(k)=3^k . If we divide b(k+1)=2^a(k+1)+1 to b(k)=2^a(k)+1 then the quotient has only 3 as a common divisor with 2^a(k)+1 . Therefore for k large enough, b(k+1) has at least one more prime divisor than b(k). (b(k+1)=b(k){2^2a(k)-2^a(k)+1}). For k large enough there b(k) has at least 1999 distinct prime divisors. Let p(1)....p(1999) be these primes. Then a(k)p(1)...p(1999) is in M (easy to prove) and has exactly 2000 distinct prime divisors.

6. Using directioned angles one gets that l(1) is parallel to BC. Thus the formed triangle must be homothetical to ABC. In order to prove the problem one must take the homotheties which take the circumcircle into the incircle of ABC. There are two such homotheties whose centres are easy to find. Take the intersections of l(1), T2T3 and H2H3 with the bisector of angle BAC. Then the bisector is perpendicular on T2T3 and using the fact that l1 and H2H3 are symetrical with respect to T2T3 one can calculate the position of l1 with respect to BC and A. Compute the position of the homothetical of BC in the given homotheties and all one has to do is check that two amounts are equal.(I have no non calculating solution)

Press here to go back to the Mathematics Page...