The2ndRomanianMasterofMathematicsCompetition–Solutions
Bucharest,Saturday,February28,2009
Problem1.??Foranypositiveintegersa1,...,ak,letn=??k??alet
n
i,andbethemultinomialcoef?cienti=1
a1,...,ak??n!
k
i=1(a.Letd=gcd(a1,...,ak)denotethegreatestcom-i
!)mondivisorofa??1,...,ak.Provethat
d
n??
naisaninteger.1,...,ak
Romania,DanSchwarz[1]Solution.Thekeyideaisthefactthatthegreatestcom-mondivisorisalinearcombinationwithintegercoef?cientsofthenumbersinvolved[2],i.e.thereexistui∈Zsuchthat
d=
??
kuiai.Buti=1
??
n??????
a=nn?1,...,a,
1,...,akaia1i?1,ai?1,ai+1,...,ak
so
d??
n??
??
k??
n???
na1,...,ak=u1
i,
i=1a1,...,ai?1,ai?1,ai+1,...,akwhichclearlyisaninteger,sincemultinomialcoef?cientsareknown(andeasytoprove)tobeinteger.??Problem2.AsetSofpointsinspacesatis?esthepropertythatallpairwisedistancesbetweenpointsinSaredistinct.GiventhatallpointsinShaveintegercoordinates(x,y,z),where1≤x,y??,z≤n,(n+2)??showthatn/3,n??the6??numberofpointsinSislessthanmin.
Romania,DanSchwarz[3]Solution.ThecriticalideaistoestimatethetotalnumberpossibleTofdistinctdistancesrealizedbypairsofpoints(x,y,z),ofintegercoordinates1≤x,y,z≤n.However,anysuchdistanceisalsorealizedbyapairanchoredat(1,1,1),fromsymmetryconsiderations.
Butthenumberofdistinctdistancesy,zequalisatmost??n??topointswithnoco-ordinatesx,1numberofdistinctdistancestopoints3=6n(n?1)(n?2);thezequalisatmost2??n??withtwoofthethreecoordinatesx,y,topoints2=n(n?1);whilethenumberofdistinctdistanceswithallthreecoordi-natesx,y,zequalisn?1,hence
T≤1n(n?1)(n?2)+n(n?1)+(n?1)<1
(n3+3n266+2n).
Ontheotherhand,thetotalnumberbetweentheNpointsinSneedsbe??Nofdistinctdistances
2??=12N(N?1)≤T,
yielding
(2N?1)2<1(4n3+12n2+8n)+1≤1
(2n??n+3??n)233
,
henceN<1??
(2n+3)??n/3+1??≤(n+2)??n/3forn≥3.One
caneasilycheck2
thattheinequalityistrueforn=2also,sincethen[4]T=3.
Ontheotherhand,sincethesquaresofthedistancescan
onlytaketheintegervaluesbetween1andthetrivialupperbound3(n?1)2(forthediagonal3(n?1),yieldingN 6.??Problem3.GivenfourpointsA1,A2,A3,A4intheplane,nothreecollinear,suchthat A1A2·A3A4=A1A3·A2A4=A1A4·A2A3, letusdenotebyOithecircumcenterof?AjAkA{i,j,k,??}={1,2,3,4}. ??,withAssumingAi=Oiforallindicesi,provethatthefourlinesAiOiareconcurrentorparallel. Bulgaria,NikolaiIvanovBeluhovSolution.(D.Schwarz)Thegiventripleequalitybeingin-variatedbyanypermutationinS4,itisenoughtoprovethatthelinesAiOifor2≤i≤4areconcurrentorparallel.Therelationscanthenbewritten A1A2A4A2 A1A3A2A3 A1A4A1A3=A,4A3 A1A4=A,2A4 A=A3A4 A.1A23A2 ConsidertheApolloniuscirclesΓkofcentersωk∈AiAj,for {i,j,k}={2,3,4},determinedbythepointA1,whichthere-foreliesonallthree,whilethepointsAklieonΓk.Moreover,thepointsωkarecollinear,sincethepointA??whichothermeetingpoint(thanAk isthe1,ifany)ofΓiandΓjful?llsA??kAjiAjkAiA??=AjAi,thus A??kAi=AkAi kAk =AAiAand A??k A??kAk AjAk A??kAj AA,kj thereforeA??alsoliesonΓk,henceallthreecirclesΓksharethesamemeetingk point(s),thustheircentersarecollinear.Now,thecircumcentersOiandOj,aswellasthepointωk,lieontheperpendicularbisectorofthesegmentA1Ak,for{i,j,k}={2,3,4}.ItfollowsthatthepairsoflinesAiAj,OiOjmeetatthecollinearpointsωk.Desargues’theoremfortheperspectivetriangles?AiAjAkand?OiOjOkyieldstheclaim.??AlternateSolution.Theauthor’soriginalsolutionmakesuseofinversionsofpolesAitoreachthesameconclusionviaDesargues,inadual-by-inversiontothesolutionabovemanner,withalotmoredetailsthanconcepts.Wefeelthatmakinguseofthewell-knownpropertiesoftheApolloniuscirclesrenderstheideainamorestrikingway.??Remark.Thereexistsaparticular(degenerate)case,whenthepointsaretheverticesofakiteofπoftheassociatedratiosis1,soa6equalangles,henceonecorrespondingApolloniuscircledegeneratestotheperpendicularbisector.This(togetherwiththeuseofDesargues)showsthedeepprojectivenatureoftheproblem,betterhandledthroughprojectivemethods. Also,thereisnoconverseimplication,sincethecaseofconcyclicpointstriviallywarrantstheconclusion,withoutful?llingthestatedcondition(asincon?ictwithPtolemy’srelation). 2 Problem4.Fora?nitesetXofpositiveintegers,let Σ(X)= 1 arctan. xx∈X?? x Lemma.Forx∈(0,π2)onehasarctanx>2. Givena?nitesetSofpositiveintegersforwhichΣ(S)<π2, showthatthereexistsatleastone?nitesetTofpositivein-tegersforwhichS?TandΣ(T)=π2. UnitedKingdom,KevinBuzzardSolution.(D.Schwarz)Wewillstep-by-stepaugmentthesetSwithpositiveintegerstn,bytakingeachtimetnastheleastpositiveintegerlargerthanmax(S),andnotalreadyused,suchthatΣ(S∪{t1,t2,...,tn})remainsatmostπ2(this 1 ispossiblesincearctant→0whent→∞).Ifatsomepointwegetexactlyπ2wearethrough,sincewehaveaugmentedStoasetTasrequired,soassumetheprocesscontinuesinde?nitely.Clearlythesequence(tn)n≥1isbuilt(strictly)increasing,soforalln≥1wehavetn+1>tn>max(S).Wewillmakesomeusefulnotations.Take,Sn+1=??πS0=S?? Sn∪{tn+1},forn∈N.Alsotakexn=tan2?Σ(Sn).Using tanα+tanβ thewell-knownformulatan(α+β)=onecan 1?tanαtanβ easilyprovebysimpleinductionthatalesserthanπ2sumofarcsofrationaltangentsisaswellanarcofrationaltan-pn gent,thereforexn=qn,withpn,qn∈N?,(pn,qn)=1.Since ???? arctanisincreasing,weneedtaketn+1≥x1inorderthatnwemayaugmentSnwithtn+1toobtainSn+1.Assumethatforalln≥1wehavex1≤tn.Sincewen????needbothtn+1≥x1andtn+1>tn≥x1,itfollowsthatnn tn+1=tn+1(theleastavailablevalue),sotk+1=t1+kfor n?1??1π arctan>allk≥0.Butthen>Σ({t1,t2,...,tn})= 2t+k1k=0 n?11??1 →∞whenn→∞,absurd(seeLemma). 2k=0t1+k ThereforethereexistssomeN≥1forwhichx1>tN, N???? 1 soxisavailablefortN+1.Moreover,foranyn≥N??xn?tn1xntn+1?1+1withtn+1=,wehavexn+1==< tn+1+xn1+xntn1 +1 ????xn1 <,sincetn+1=x1impliesxntn+1?1 andsowecantaketn+1=x1inde?nitelyforn≥N.Nown ?? 1 xn N Proof.Westartbyprovingthatundergivenconditionone sinxxx2x hassinx>tan2,inturnequivalentto2sincos>, 22cosx22cos2x2?1>0,and?nallycosx>0,patentlytrue. Now,arctanisincreasing,henceappliedtotheabove,togetherwiththewell-knowninequalityx>sinx,truefor x allx>0,yieldsarctanx>arctansinx>arctantanx2=2.??1 >21Asacorollary,arctannn,forallpositiveintegers n,inequalityusedtoyieldthedivergenceoftheseries??1 arctanintheabovesolution. nn≥1 Remark.Theabovesolutionshowsthatitisirrelevant π??1 thatwestartwiththearc?arctan;infactwemay 2s∈Ss statetheproblemlikethis Provethatforanyarcα∈(0,π2)ofsomerationaltangentτ=tanα,andany?nitesetSofdistinctpositiveintegers,thereexistssome?nitesetTofdistinctpositiveintegerssuchthatT∩S=??and ?? t∈T arctan 1 =α.t TheproblemisstronglyreminiscentofastrengthenedformofthefamousEgyptianfraction[5]theorem Provethatforanyrationalnumberr∈(0,1),andany?nitesetSofdistinctpositiveintegers,thereexistsa?nitesetTofdistinctpositiveintegerssuchthatT∩S=??and ??1 =r.t∈Tt Alltheingredientsarethere:thegreedyalgorithm,goingbeyondthelargestelementofS,usingthedivergenceofthe ??1 series,andthe(Fermat)in?nitedescentmethodofa nn≥1 (strictly)decreasingsequenceofpositiveintegers. Infact,itisenoughtoconsidera(strictly)increasingfunc-tionf:Q+→R+withthepropertiesthatthereexistsafunc-tion?:Q+×Q+→Q+suchthatf(r)?f(s)=??f(???(r,s))forn??1any0≤s n→∞x→0kk=1 Moreover,weneedthat?(r,s)hasnotlargernumeratorthanr?s,andnotlesserdenominator.ThentheEgyptianfractionmethodextendsperfectly.Orf(x)=arctanxand x?y ?(x,y)=1+xyconformtothismodel.END weusethefactthatxn= p n pn+1pntn+1?qnqn?tn+1 Then==,hencepn+1≤pn1 qn+1qt+p1+qnnn+1ntn+1 ????qnqn pntn+1?qn pnpn Thereforethesequence(pn)n≥1ofthenumeratorsofxneventuallybecomes(strictly)decreasing,absurdforanyse-quenceofpositiveintegers.?? pn qn.1 [1]Basedonapropertyofquasi-CatalannumbersofJ.Conway, see[GUY,R.K.,UnsolvedProblemsinNumberTheory]. [2]EasilyprovenbyinductionfromtheclassicalBézout’srelation gcd(M,N)=uM+vNforsomeintegersu,v. [3]A3-dimensionalextrapolationofaplanelatticepointscase studyofP.Erd?sandR.K.Guy. [4]AnexampleofN=3pointsforn=2is(1,1,1),(2,2,1),(2,2,2); andofN=4pointsforn=3is(1,1,1),(1,1,2),(2,2,1),(2,3,3).[5]AnEgyptianfractioniswrittenasa?nitesumoffractionswith allunitnumeratorsandalldistinctdenominators.Suchfrac-tionswereusedbyancientEgyptians,asapparentintheRhindPapyrus,buttheiruseisdiscontinuedtoday.
