INMO 2021

1 INMO 2021 Official SolutionsProblem 2is an integer, and letm1,n1,m2,n2, ,mr,nrbe2rintegerssuch that|minj mjni|= 1for any two integersiandjsatisfying1 i < j r. Determine the maximum possiblevalue ,n1,m2,n2be integers satisfyingm1n2 m2n1= 1. By changing thesigns ofm2,n2if need be, we may assume thatm1n2 m2n1= ,n3are integers satisfyingm1n3 m3n1= 1, again we may assume (by changingtheir signs if necessary) thatm1n3 m3n1= (n2 n3) =n1(m2 m3).Asm1,n1are relatively prime,m1dividesm2 m3; say,m2 m3=m1afor some integera. Thus, we getn2 n3=n1a. In other words,m3=m2 m1a , n3=n2 , ifm2n3 n2m3= 1, we get 1 =m2(n2 n1a) n2(m2 m1a) = (m1n2 m2n1)a= ,m3=m2 m1a=m2 m1,n3=n2 n1a=n2 if we were to have another pair of integersm4,n4such thatm1n4 n1m4= 1,we may assume thatm1n4 n1m4= 1. As seen above,m4=m2 m1,n4=n2 n1.

2 But thenm3n4 n3m4= (m2 m1)(n2 n1) (n2 n1)(m2 m1) = , there can be only 3 pairs of such there do exist many sets of 3 pairs is easy to see; for instance,(1,0),(1,1),(0,1)is such a is clear thatrcan be3due to the valid solutionm1= 1,n1=1,m2= 1,n2= 2,m3= 2,n3= possible, letr >3. We observe that:m1n2n3 m2n1n3= n3m2n3n1 m3n2n1= n1m3n1n2 m1n3n2= n2 Adding, we get n1 n2 n3= 0; which forces at least one ofn1,n2,n3to be even; WLOG letn1be the argument for indices2,3,4, we deduce that at least one ofn2,n3,n4iseven; WLOG letn2be even. This leads to a contradiction, since|m1n2 m2n1|= 1cannotbe even. Hencer >3is not possible, as all pairs of integers(a,b)so that each of the two cubic polynomialsx3+ax+bandx3+bx+ahas all the roots to be only such pair is(0,0), which clearly works.

3 To prove this is the only one,let us prove an auxiliary result , , are reals so that + + = 0and| |,| |,| | 2, then| + + |<| |. two of these reals have the same sign; WLOG, suppose >0. Then = ( + ), so by substituting this,| + + |=| 2+ 2+ |,| |=| ( + )|.So we simply need to show| ( + )|>| 2+ 2+ |. Since| | 2and| | 2, we have| ( + )|=| || ( + )| 2| ( + )|,| ( + )|=| || ( + )| 2| ( + )|.Adding these and using triangle inequality,2| ( + )| 2| ( + )|+ 2| ( + )| 2| ( + ) + ( + )| 2( 2+ 2+ 2 )>2( 2+ 2+ )= 2| 2+ 2+ |.Here we have used the fact that 2+ 2+ 2 = ( + )2and 2+ 2+ =( + 2)2+3 24are both nonnegative. This proves our our main problem, suppose the roots ofx3+ax+bare the integersr1,r2,r3and theroots ofx3+bx+aare the integerss1,s2,s3. By Vieta s relations, we haver1+r2+r3= 0 =s1+s2+s3r1r2+r2r3+r3r1=a= s1s2s3s1s2+s2s3+s3s1=b= r1r2r3If all six of these roots had an absolute value of at least2, by our lemma, we would have|b|=|s1s2+s2s3+s3s1|<|s1s2s3|=|r1r2+ r2r3+r3r1|<|r1r2r3|=|b|,which is absurd.

4 Thus at least one of them is in the set{0,1, 1}; WLOG, suppose it Ifr1= 0, thenr2= r3, sob= 0. Then the roots ofx3+bx+a=x3+aare preciselythe cube roots of a, and these are all real only fora= 0. Thus(a,b) = (0,0), whichis a Ifr1= 1, then 1 a+b= 0, soaandbcan t both be even. Ifa= s1s2s3is odd,thens1,s2,s3are all odd, sos1+s2+s3cannot be zero. Similarly, ifbis odd, we geta proof is now only such pair is(0,0), which clearly works. Let us prove thisis the only one. In what follows, we use 2(n)to denote the largest integerkso that2k|nfor any non-zeron one of the cubics has0as a root, say the first one, then03+ 0 a+b= 0, sob= the roots ofx3+bx+a=x3+aare precisely the cube roots of a, and these are allreal only fora= 0. Thus(a,b) = (0,0).So suppose none of the roots are zero.

5 Take the cubicx3+ax+b, and suppose its rootsarex,y,z. We cannot have 2(x) = 2(y) = 2(z); indeed, if we hadx= 2kx1,y= 2ky1,z=2kz1for oddx1,y1,z1, then0 =x+y+z= 2k(x1+y1+z1).Butx1+y1+z1is odd, and hence non-zero, so this cannot we can assume WLOG that 2(x)> 2(y). Then the third root is (x+y). Similarly,the three roots ofx3+bx+acan be written asp,q, (p+q)where 2(p)> 2(q). By Vieta srelations,xy x(x+y) y(x+y) = (x2+xy+y2) =a=pq(p+q)pq p(p+q) q(p+q) = (p2+pq+q2) =b=xy(x+y)2 Supposex= 2kx1andy= 2`y1for oddx1,y1andk > `; in particulark >0. Thenxy(x+y) = 2kx1 2`y1 (2kx1+ 2`y1) = 2k+2`x1y1(2k `x1+y1).Herex1y1(2k `x1+y1)is clearly odd, so 2(xy(x+y)) =k+ 2`.Also,x2+xy+y2= 22kx21+ 2kx1 2`y1+ 22`y21= 22`(22k 2`x21+ 2k `x1y1+y21).Again, all the terms in the second factor are even excepty21, so the entire factor is means 2(x2+xy+y2) = 2`.

6 Therefore 2(xy(x+y))> 2(x2+xy+y2).Similarly, one may show 2(pq(p+q))> 2(p2+pq+q2).But then 2(b) = 2(xy(x+y))> 2(x2+xy+y2) = 2(pq(p+q))> 2(p2+pq+q2) = 2(b).Here we have used the fact that 2(n) = 2( n)for any integern. But this is a contradic-tion, proving our marks2021points on the plane such that no three are collinear, anddraws all possible line segments joining these. He then chooses any1011of these linesegments, and marks their midpoints. Finally, he chooses a line segment whose mid-point is not marked yet, and challenges Vikram to construct its midpoint usingonlyastraightedge. Can Vikram always complete this challenge?Note:A straightedge is an infinitely long ruler without markings, which can only beused to draw the line joining any two given distinct answer is yes.

7 To prove this, we will first prove two lemmas:Lemma 1 Given any two pointsA,B, their midpointM, and any pointC, Vikram candraw a line parallel on lineABwe are already done. If not, extendBCtoXas shown, drawP=AC XM, and then drawD=BP AX. We claimCDis the desired line. Indeed,using Ceva s theorem on triangleABXand the factAM=MB, we see thatAMMB BCCX XDDA= 1 = XCCB= meansCD 1 Lemma 23 Lemma 2 Given two non-parallel segmentsAB,BCand their midpointsM,N, Vikramcan draw the midpoint of any other firstXYis not parallel toABorBC. Using lemma 1, draw lines`1and`2throughXparallel toABandBCrespectively, and similarly drawm1andm2throughYparallel toABandBCrespectively. If we drawP=`1 m2andQ=`2 m1, thenXPY Qis a parallelogram, so intersectingPQandXYgives the midpoint for the remaining case, one can drawACand construct the midpointPofACbythe construction described above.

8 SinceXYcan be parallel to at most one of the sidesAB,BCandAC, we can pick the two non-parallel sides, and use the above constructionto draw the midpoint for the main problem, note that if no two of the1011chosen segments share anendpoint, then we have at least2 1011 = 2022distinct endpoints, a contradiction. Thusthere must be two segmentsABandBCwhich have their midpoints marked. Since nothree of the chosen2021points were collinear,ABandBCare not parallel, so usinglemma 2, Vikram can construct the midpoint of any other segment, in particular, thesegment chosen by SolutionAs in the previous solution, note that there existABandACwhosemidpointsC andB are marked. Using the straightedge, Vikram can draw the two medi-ansAC andAB and obtain their intersection, the centroidGof4 ABC.

9 Now intersectingAGwithBCgivesA , the midpoint a pointPnot onAB,AC, Vikram can draw the midpoint ||ACandPC||AB, thenPBACis a parallelogram, in which caseA constructedabove is the midpoint ofPA. Without loss of generality, we may assumePB BA CP PDD Q Using the straightedge, one can mark the pointsD=PB ACandPB A C =D .SinceCA||A C , we haveBD D D=BC C A= 1,soD is the midpoint ofBD. Now in4 ABD, two midpointsC andD are known, so themidpoint ofQ ofADcan be constructed using the centroid construction outlined =C Q PA; this exists asC Q ||BP AP. As before,C P ||BP, soAP P P=AC C B= 1,which meansP is the desired midpoint suppose we need to find the midpoint ofPQ. IfP,Qare different points fromA,then one can draw the midpoints ofAPandAQusing the lemma. Then by using thecentroid of4 APQ, one can find the midpoint ofPQas we did forBC.

10 IfPorQisA, theabove lemma immediately yields the required 4A Magician and a Detective play a game. The Magician lays down cardsnumbered from1to52face-down on a table. On each move, the Detective can pointto two cards and inquire if the numbers on them are consecutive. The Magician repliestruthfully. After a finite number of moves the Detective points to two cards. She wins ifthe numbers on these two cards are consecutive, and loses that the Detective can guarantee a win if and only if she is allowed to ask atleast 50 for the Detective:Pick a cardAand compare against all others exceptone. If he ever gets a Yes", that pair works; else the remaining card is consecutive withA. This process takes at for the Magician:We show that it is not always possible to obtain a Yes" in50turns, hence showing that49turns are not enough to figure out a consecutive pair.