52 Mathematical Olympiad - imo-official.org

1 52nd International Mathematical Olympiad12 24 July 2011 AmsterdamThe NetherlandsInternationalMathematicalOlym piad Amsterdam 2011 IMO2011 AmsterdamProblem Shortlistwith Solutions52nd InternationalMathematical Olympiad12-24 July 2011 AmsterdamThe NetherlandsProblem shortlistwith solutionsIMPORTANTIMO regulation:these shortlist problems have tobe kept strictly confidentialuntil IMO problem selection committeeBart de Smit (chairman), Ilya Bogdanov, Johan Bosman,Andries Brouwer, Gabriele Dalla Torre, G eza K os,Hendrik Lenstra, Charles Leytem, Ronald van Luijk,Christian Reiher, Eckard Specht, Hans Sterk, Lenny TaelmanThe committee gratefully acknowledges the receipt of 142 problem proposalsby the following 46 countries.

2 Armenia, Australia, Austria, Belarus, Belgium,Bosnia and Herzegovina, Brazil, Bulgaria, Canada, Colombia,Cyprus, Denmark, Estonia, Finland, France, Germany, Greece,Hong Kong, Hungary, India, Islamic Republic of Iran, Ireland, Israel,Japan, Kazakhstan, Republic of Korea, Luxembourg, Malaysia,Mexico, Mongolia, Montenegro, Pakistan, Poland, Romania,Russian Federation, Saudi Arabia, Serbia, Slovakia, Slovenia,Sweden, Taiwan, Thailand, Turkey, Ukraine, United Kingdom,United States of AmericaAlgebraProblem shortlist52nd IMO 2011 AlgebraA1A1 For any setA={a1, a2, a3, a4}of four distinct positive integers with sumsA=a1+a2+a3+a4,letpAdenote the number of pairs (i, j) with 1 i < j 4 for whichai+ajdividessA.

3 Amongall sets of four distinct positive integers, determine those setsAfor whichpAis all sequences (x1, x2, .. , x2011) of positive integers such that for every positive inte-gernthere is an integerawithxn1+ 2xn2+ + 2011xn2011=an+1+ all pairs (f, g) of functions from the set of real numbers to itself that satisfyg(f(x+y)) =f(x) + (2x+y)g(y)for all real all pairs (f, g) of functions from the set of positive integers to itself that satisfyfg(n)+1(n) +gf(n)(n) =f(n+ 1) g(n+ 1) + 1for every positive integern. Here,fk(n) meansf(f(.. f|{z}k(n)..)).A5A5 Prove that for every positive integern, the set{2,3,4.}

4 ,3n+ 1}can be partitioned intontriples in such a way that the numbers from each triple are the lengths of the sides of someobtuse IMO 2011 Problem shortlistAlgebraA6A6 Letfbe a function from the set of real numbers to itself that satisfiesf(x+y) yf(x) +f(f(x))for all real numbersxandy. Prove thatf(x) = 0 for allx ,b, andcbe positive real numbers satisfying min(a+b, b+c, c+a)> 2 anda2+b2+c2= thata(b+c a)2+b(c+a b)2+c(a+b c)2 3(abc) shortlist52nd IMO 2011 CombinatoricsC1C1 Letn >0 be an integer. We are given a balance andnweights of weight 20, 21, .. ,2n 1.

5 In asequence ofnmoves we place all weights on the balance. In the first move we choose a weightand put it on the left pan. In each of the following moves we choose one of the remainingweights and we add it either to the left or to the right pan. Compute the number of ways inwhich we can perform thesenmoves in such a way that the right pan is never heavier than theleft that 1000 students are standing in a circle. Prove that there exists an integerkwith100 k 300 such that in this circle there exists a contiguous group of 2kstudents, for whichthe first half contains the same number of girls as the second a finite set of at least two points in the plane.

6 Assume that no three points ofSarecollinear. By awindmillwe mean a process as follows. Start with a line going through apointP S. Rotate clockwise around thepivotPuntil the line contains another pointQofS. The pointQnow takes over as the new pivot. This process continues indefinitely, withthe pivot always being a point that for a suitableP Sand a suitable starting line containingP, the resultingwindmill will visit each point ofSas a pivot infinitely the greatest positive integerkthat satisfies the following property: The set of positiveintegers can be partitioned intoksubsetsA1, A2.

7 , Aksuch that for all integersn 15 andalli {1,2, .. , k}there exist two distinct elements ofAiwhose sum IMO 2011 Problem shortlistCombinatoricsC5C5 Letmbe a positive integer and consider a checkerboard consisting ofmbymunit the midpoints of some of these unit squares there is an ant. At time 0, each ant startsmoving with speed 1 parallel to some edge of the checkerboard. When two ants moving inopposite directions meet, they both turn 90 clockwise and continue moving with speed more than two ants meet, or when two ants moving in perpendicular directions meet,the ants continue moving in the same direction as before they met.

8 When an ant reaches oneof the edges of the checkerboard, it falls off and will not all possible starting positions, determine the latest possible moment at which thelast ant falls off the checkerboard or prove that such a moment does not necessarily a positive integer and letW=.. x 1x0x1x2..be an infinite periodic word consistingof the lettersaandb. Suppose that the minimal periodNofWis greater than finite nonempty wordUis said toappearinWif there exist indicesk such thatU=xkxk+1.. x . A finite wordUis calledubiquitousif the four wordsUa,Ub,aU, andbUall appear inW.

9 Prove that there are at leastnubiquitous finite nonempty a square table of 2011 by 2011 cells we place a finite number of napkins that each covera square of 52 by 52 cells. In each cell we write the number of napkinscovering it, and werecord the maximal numberkof cells that all contain the same nonzero number. Consideringall possible napkin configurations, what is the largest value ofk?7 GeometryProblem shortlist52nd IMO 2011 GeometryG1G1 LetABCbe an acute triangle. Let be a circle whose centerLlies on the sideBC. Supposethat is tangent toABatB and toACatC . Suppose also that the circumcenterOof thetriangleABClies on the shorter arcB C of.

10 Prove that the circumcircle ofABCand meet at two a non-cyclic quadrilateral. LetO1andr1be the circumcenter and thecircumradius of the triangleA2A3A4. DefineO2,O3,O4andr2,r3,r4in a similar way. Provethat1O1A21 r21+1O2A22 r22+1O3A23 r23+1O4A24 r24= a convex quadrilateral whose sidesADandBCare not parallel. Suppose that thecircles with diametersABandCDmeet at pointsEandFinside the quadrilateral. Let Ebethe circle through the feet of the perpendiculars fromEto the linesAB,BC, andCD. Let Fbe the circle through the feet of the perpendiculars fromFto the linesCD,DA, that the midpoint of the segmentEFlies on the line through the two intersection pointsof Eand an acute triangle with circumcircle.