2024罗马尼亚大师杯解答

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.

百度搜索“70edu”或“70教育网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，70教育网，提供经典综合文库2024罗马尼亚大师杯解答在线全文阅读。