Shortlisted Problems with Solutions

1 Shortlisted Problems with Solutions53rdInternational Mathematical OlympiadMar del Plata, Argentina 2012 Note of ConfidentialityThe Shortlisted Problems should be keptstrictly confidential until IMO 2013 Contributing CountriesThe Organizing Committee and the Problem Selection Committee of IMO2012 thank thefollowing 40 countries for contributing 136 problem proposals:Australia, Austria, Belarus, Belgium, Bulgaria, Canada, Cyprus,Czech Republic, Denmark, Estonia, Finland, France, Germany,Greece, Hong Kong, India, Iran, Ireland, Israel, Japan,Kazakhstan, Luxembourg, Malaysia, Montenegro, Netherlands,Norway, Pakistan, Romania, Russia, Serbia, Slovakia, Slovenia,South Africa, South Korea, Sweden, Thailand, Ukraine,United Kingdom, United States of America, UzbekistanProblem Selection CommitteeMart n Avenda noCarlos di FioreG eza K osSvetoslav all the functionsf.

2 Z Zsuch thatf(a)2+f(b)2+f(c)2= 2f(a)f(b) + 2f(b)f(c) + 2f(c)f(a)for all integersa,b,csatisfyinga+b+c= the sets of integers and rationals ) Does there exist a partition ofZinto three non-empty subsetsA, B, Csuch that the setsA+B,B+C,C+Aare disjoint?b) Does there exist a partition ofQinto three non-empty subsetsA, B, Csuch that the setsA+B,B+C,C+Aare disjoint?HereX+Ydenotes the set{x+y|x X, y Y}, forX, Y ZandX, Y , .. , anben 1 positive real numbers, wheren 3, such thata2a3 an= that(1 +a2)2(1 +a3)3 (1 +an)n> two nonzero polynomials with integer coefficients and degf > that for infinitely many primespthe polynomialpf+ghas a rational root. Provethatfhas a rational all functionsf:R Rthat satisfy the conditionsf(1 +xy) f(x+y) =f(x)f(y) for allx, y Randf( 1)6= :N Nbe a function, and letfmbefappliedmtimes.

3 Suppose that foreveryn Nthere exists ak Nsuch thatf2k(n) =n+k, and letknbe the smallest that the sequencek1, k2, ..is say that a functionf:Rk Ris a metapolynomial if, for some positive integersmandn, it can be represented in the formf(x1, .. , xk) = maxi=1,..,mminj=1,..,nPi,j(x1, .. , xk)wherePi,jare multivariate polynomials. Prove that the product of two metapolynomials is alsoa positive integers are written in a row. Iteratively, Alice chooses two adjacentnumbersxandysuch thatx > yandxis to the left ofy, and replaces the pair (x, y) by either(y+ 1, x) or (x 1, x). Prove that she can perform only finitely many such 1 be an integer. What is the maximum number of disjoint pairs of elements of theset{1,2.}

4 , n}such that the sums of the different pairs are different integers notexceedingn? a 999 999 square table some cells are white and the remaining ones are the number of triples (C1, C2, C3) of cells, the first two in the same row and the last two inthe same column, withC1andC3white andC2red. Find the maximum valueTcan a game withN 2012 coins and 2012 boxes arranged around acircle. InitiallyAdistributes the coins among the boxes so that there is at least 1 coinin eachbox. Then the two of them make moves in the orderB, A, B, A, ..by the following rules: On every move of hisBpasses 1 coin from every box to an adjacent box. On every move of hersAchooses several coins that werenotinvolved inB s previousmove and are in different boxes.

5 She passes every chosen coin to anadjacent s goal is to ensure at least 1 coin in each box after every move of hers, regardless ofhowBplays and how many moves are made. Find the leastNthat enables her to columns and the rows of a 3n 3nsquare board are numbered 1,2, .. ,3n. Everysquare (x, y) with 1 x, y 3nis colored asparagus, byzantium or citrine according as themodulo 3 remainder ofx+yis 0, 1 or 2 respectively. One token colored asparagus, byzantiumor citrine is placed on each square, so that there are 3n2tokens of each that one can permute the tokens so that each token is moved to a distance ofat mostdfrom its original position, each asparagus token replaces a byzantium token, eachbyzantium token replaces a citrine token, and each citrine token replaces an asparagus that it is possible to permute the tokens so that each token ismoved to a distance of atmostd+ 2 from its original position, and each square contains a token with the same color asthe fixed positive integers.

6 In the liar s guessing game, Amy chooses integersxandNwith 1 x N. She tells Ben whatNis, but not whatxis. Ben may then repeatedlyask Amy whetherx Sfor arbitrary setsSof integers. Amy will always answer withyesorno,but she might lie. The only restriction is that she can lie at mostktimes in a row. After hehas asked as many questions as he wants, Ben must specify a set ofat mostnpositive in this set he wins; otherwise, he loses. Prove that:a) Ifn 2kthen Ben can always ) For sufficiently largekthere existn that Ben cannot guarantee a are given 2500points on a circle labeled 1,2, .. ,2500in some order. Prove thatone can choose 100 pairwise disjoint chords joining some of these points so that the 100 sumsof the pairs of numbers at the endpoints of the chosen chords the triangleABCthe pointJis the center of the excircle opposite toA.

7 This excircleis tangent to the sideBCatM, and to the linesABandACatKandLrespectively. ThelinesLMandBJmeet atF, and the linesKMandCJmeet atG. LetSbe the point ofintersection of the linesAFandBC, and letTbe the point of intersection of the linesAGandBC. Prove thatMis the midpoint a cyclic quadrilateral whose diagonalsACandBDmeet atE. Theextensions of the sidesADandBCbeyondAandBmeet atF. LetGbe the point such thatECGDis a parallelogram, and letHbe the image ofEunder reflection inAD. Prove thatD,H,F,Gare an acute triangleABCthe pointsD,EandFare the feet of the altitudes throughA,BandCrespectively. The incenters of the trianglesAEFandBDFareI1andI2respectively ;the circumcenters of the trianglesACI1andBCI2areO1andO2respective ly.

8 Prove thatI1I2andO1O2are a triangle withAB6=ACand circumcenterO. The bisector of BACintersectsBCatD. LetEbe the reflection ofDwith respect to the midpoint ofBC. The linesthroughDandEperpendicular toBCintersect the that the quadrilateralBXCYis a triangle with BCA= 90 , and letC0be the foot of the altitudefromC. Choose a pointXin the interior of the segmentCC0, and letK, Lbe the points onthe segmentsAX, BXfor whichBK=BCandAL=ACrespectively. Denote byMtheintersection ofALandBK. Show thatMK= a triangle with circumcenterOand incenterI. The pointsD,EandFonthe sidesBC,CAandABrespectively are such thatBD+BF=CAandCD+CE= circumcircles of the trianglesBF DandCDEintersect atP6=D. Prove thatOP= a convex quadrilateral with non-parallel sidesBCandAD.

9 Assumethat there is a pointEon the sideBCsuch that the quadrilateralsABEDandAECD arecircumscribed. Prove that there is a pointFon the sideADsuch that the quadrilateralsABCFandBCDFare circumscribed if and only ifABis parallel a triangle with circumcircle and a line without common points with .Denote byPthe foot of the perpendicular from the center of to . The side-linesBC, CA, ABintersect at the pointsX, Y, Zdifferent fromP. Prove that the circumcircles of the trianglesAXP, BY PandCZPhave a common point different fromPor are mutually tangent admissible a setAof integers that has the following property:Ifx, y A(possiblyx=y) thenx2+kxy+y2 Afor every all pairsm, nof nonzero integers such that the only admissible set containing bothmandnis the set of all all triples (x, y, z) of positive integers such thatx y zandx3(y3+z3) = 2012(xyz+ 2).

10 All integersm 2 such that everynwithm3 n m2divides the binomialcoefficient nm 2n . integerais called friendly if the equation (m2+n)(n2+m) =a(m n)3has asolution over the positive ) Prove that there are at least 500 friendly integers in the set{1,2, .. ,2012}.b) Decide whethera= 2 is a nonnegative integerndefinerad(n) = 1 ifn= 0 orn= 1, andrad(n) =p1p2 pkwherep1< p2< < pkare all prime factors ofn. Find all polynomialsf(x) with nonnegativeinteger coefficients such thatrad(f(n)) dividesrad(f(nrad(n))) for every nonnegative positive integers. Ifx2n 1 is divisible by 2ny+ 1 for every positiveintegern, prove thatx= alln Nfor which there exist nonnegative integersa1, a2.