inequalitywww.666abcd

Volume11,Number1February2006–March2006Muirhead'sInequalityLauChiHinOlympiadCornerBelowwasSlovenia'sSelectionExaminationsfortheIMO2005.
FirstSelectionExaminationProblem1.
LetMbetheintersectionofdiagonalsACandBDoftheconvexquadrilateralABCD.
ThebisectorofangleACDmeetstherayBAatthepointK.
ProvethatifMA·MC+MA·CD=MB·MD,then∠BKC=∠BDC.
Problem2.
LetR+bethesetofallpositiverealnumbers.
Findallfunctionsf:R+→R+suchthatx2(f(x)+f(y))=(x+y)f(f(x)y)holdsforanypositiverealnumbersxandy.
Problem3.
Findallpairsofpositiveintegers(m,n)suchthatthenumbersm24nandn24mareperfectsquares.
SecondSelectionExaminationProblem1.
Howmanysequencesof2005termsaretheresuchthatthefollowingthreeconditionshold:(a)nosequencehasthreeconsecutivetermsequaltoeachother,(b)everytermofeverysequenceisequalto1or1,and(continuedonpage4)Editors:張百康(CHEUNGPak-Hong),MunsangCollege,HK高子眉(KOTsz-Mei)梁達榮(LEUNGTat-Wing)李健賢(LIKin-Yin),Dept.
ofMath.
,HKUST吳鏡波(NGKeng-PoRoger),ITC,HKPUArtist:楊秀英(YEUNGSau-YingCamille),MFA,CUAcknowledgment:ThankstoElinaChiu,Math.
Dept.
,HKUSTforgeneralassistance.
On-line:http://www.
math.
ust.
hk/mathematical_excalibur/Theeditorswelcomecontributionsfromallteachersandstudents.
Withyoursubmission,pleaseincludeyourname,address,school,email,telephoneandfaxnumbers(ifavailable).
Electronicsubmissions,especiallyinMSWord,areencouraged.
ThedeadlineforreceivingmaterialforthenextissueisApril16,2006.
Forindividualsubscriptionforthenextfiveissuesforthe05-06academicyear,sendusfivestampedself-addressedenvelopes.
Sendallcorrespondenceto:Dr.
Kin-YinLIDepartmentofMathematicsTheHongKongUniversityofScienceandTechnologyClearWaterBay,Kowloon,HongKongFax:(852)23581643Email:makyli@ust.
hkMuirhead'sinequalityisanimportantgeneralizationoftheAM-GMinequality.
Itisapowerfultoolforsolvinginequalityproblem.
Firstwegiveadefinitionwhichisageneralizationofarithmeticandgeometricmeans.
Definition.
Letx1,x2,…,xnbepositiverealnumbersandp=(p1,p2,…,pn)n.
Thep-meanofx1,x2,…,xnisdefinedby,!
1][)()2()1(21∑∈=nnSpnppxxxnpσσσσLwhereSnisthesetofallpermutationsof{1,2,…,n}.
(Thesummationsignmeanstosumn!
terms,onetermforeachpermutationσinSn.
)Forexample,∑==niixn11)]0,,0,1[(Kisthearithmeticmeanofx1,x2,…,xnandnnnnxxxnnn/1/12/11)]/1,,/1,/1[(LK=istheirgeometricmean.
Nextweintroducetheconceptofmajorizationinn.
Letp=(p1,p2,…,pn)andq=(q1,q2,…,qn)nsatisfyconditions1.
p1≥p2≥≥pnandq1≥q2≥≥qn,2.
p1≥q1,p1+p2≥q1+q2,…,p1+p2++pn1≥q1+q2++qn1and3.
p1+p2++pn=q1+q2++qn.
Thenwesay(p1,p2,…,pn)majorizes(q1,q2,…,qn)andwrite(p1,p2,…,pn)(q1,q2,…,qn).
Theorem(Muirhead'sInequality).
Letx1,x2,…,xnbepositiverealnumbersandp,qn.
Ifpq,then[p]≥[q].
Furthermore,forp≠q,equalityholdsifandonlyifx1=x2==xn.
Since(1,0,…,0)(1/n,1/n,…,1/n),AM-GMinequalityisaconsequence.
Example1.
Foranya,b,c>0,provethat(a+b)(b+c)(c+a)≥8abc.
Solution.
Expandingbothsides,thedesiredinequalityisa2b+a2c+b2c+b2a+c2a+c2b≥6abc.
Thisisequivalentto[(2,1,0)]≥[(1,1,1)],whichistruebyMuirhead'sinequalitysince(2,1,0)(1,1,1).
Forthenextexample,wewouldliketopointoutausefultrick.
Whentheproductofx1,x2,…,xnis1,wehave[(p1,p2,…,pn)]=[(p1–r,p2–r,…,pn–r)]foranyrealnumberr.
Example2.
(IMO1995)Foranya,b,c>0withabc=1,provethat.
23)(1)(1)(1333≥+++++bacacbcbaSolution.
Multiplyingbythecommondenominatorandexpandingbothsides,thedesiredinequalityis)(2)(2)(2233233233343434343434444444bacacbcbaabcbaccabacbbcacbaaccbba+++++++++++345345345345(3cabacbbcacba+++≥.
6)444345345cbaabcbac+++Thisisequivalentto[(4,4,0)]+2[(4,3,1)]+[(3,3,2)]≥3[(5,4,3)]+[(4,4,4)].
Note4+4+0=4+3+1=3+3+2=8,but5+4+3=4+4+4=12.
Sowecansetr=4/3andusethetrickabovetoget[(5,4,3)]=[(11/3,8/3,5/3)]andalso[(4,4,4)]=[(8/3,8/3,8/3)].
Observethat(4,4,0)(11/3,8/3,5/3),(4,3,1)(11/3,8/3,5/3)and(3,3,2)(8/3,8/3,8/3).
SoapplyingMuirhead'sinequalitytothesethreemajorizationsandaddingtheinequalities,wegetthedesiredinequality.
MathematicalExcalibur,Vol.
11,No.
1,Feb.
06-Mar.
06Page2Example3.
(1998IMOShortlistedProblem)Foranyx,y,z>0withxyz=1,provethat.
43)1)(1()1)(1()1)(1(333≥++++++++yxzxzyzyxSolution.
Multiplyingbythecommondenominatorandexpandingbothsides,thedesiredinequalityis4(x4+y4+z4+x3+y3+z3)≥3(1+x+y+z+xy+yz+zx+xyz).
Thisisequivalentto4[(4,0,0)]+4[(3,0,0)]≥[(0,0,0)]+3[(1,0,0)]+3[(1,1,0)]+[(1,1,1)].
Forthis,weapplyMuirhead'sinequalityandthetrickasfollow:[(4,0,0)]≥[(4/3,4/3,4/3)]=[(0,0,0)],3[(4,0,0)]≥3[(2,1,1)]=3[(1,0,0)],3[(3,0,0)]≥3[(4/3,4/3,1/3)]=3[(1,1,0)]and[(3,0,0)]≥[(1,1,1)].
Addingthese,wegetthedesiredinequality.
Remark.
Forthefollowingexample,wewillmodifythetrickabove.
Incasexyz≥1,wehave[(p1,p2,p3)]≥[(p1–r,p2–r,p3–r)]foreveryr≥0.
Also,wewillusethefollowingFact.
Forp,qn,wehave.
22][][+≥+qpqpThisisbecausebytheAM-GMinequality,.
22/)()(2/)()1()()1()()1(1111nnnnqpnqpqnqpnpxxxxxx++≥+σσσσσσLLLSummingoverσSnanddividingbyn!
,wegettheinequality.
Example4.
(2005IMO)Foranyx,y,z>0withxyz≥1,provethat.
0225252252522525≥++++++++yxzzzxzyyyzyxxxSolution.
Multiplyingbythecommondenominatorandexpandingbothsides,thedesiredinequalityisequivalentto[(9,0,0)]+4[(7,5,0)]+[(5,2,2)]+[(5,5,5)]≥[(6,0,0)]+[(5,5,2)]+2[(5,4,0)]+2[(4,2,0)]+[(2,2,2)].
Toprovethis,wenotethat(1)[(9,0,0)]≥[(7,1,1)]≥[(6,0,0)](2)[(7,5,0)]≥[(5,5,2)](3)2[(7,5,0)]≥2[(6,5,1)]≥2[(5,4,0)](4)[(7,5,0)]+[(5,2,2)]≥2[(6,7/2,1)]≥2[(11/2,7/2,3/2)]≥2[(4,2,0)](5)[(5,5,5)]≥[(2,2,2)],where(1)and(3)arebyMuirhead'sinequalityandtheremark,(2)isbyMuirhead'sinequality,(4)isbythefact,Muirhead'sinequalityandtheremarkand(5)isbytheremark.
Consideringthesumoftheleftmostpartsoftheseinequalitiesisgreaterthanorequaltothesumoftherightmostpartsoftheseinequalities,wegetthedesiredinequalities.
AlternateSolution.
Since)(22232522525zyxxxxzyxxx++++=,0))(()()1(2252222223≥+++++zyxzyxxzyxwehave225252252522525yxzzzxzyyyzyxxx++++++++)()()(222325222325222325yxzzzzxzyyyyzyxxxx++++++++≥)111(1222222zzyyxxzyx++++≥)(1222222xyzxyzzyxzyx++++≥.
0)(2)()()(222222≥++++=zyxxzzyyxProofsofMuirhead'sInequalityKinYinLiLetpqandp≠q.
Fromi=1ton,thefirstnonzeropi–qiispositivebycondition2ofmajorization.
Thenthereisanegativepi–qilaterbycondition3.
Itfollowsthattherearejqj,pk70·73·71>713.
SoS>3·71=213.
Therefore,214istheanswer.
Problem242.
Provethatforeverypositiveintegern,7isadivisorof3n+n3ifandonlyif7isadivisorof3nn3+1.
(Source:1995BulgarianWinterMathCompetition)Solution.
CHANTszLung(HKUMathPGYear1),G.
R.
A.
20MathProblemGroup(Roma,Italy),D.
KippJOHNSON(ValleyCatholicSchool,Beaverton,OR,USA,teacher),KWOKLoYan(CarmelDivineGraceFoundationSecondarySchool,Form6),ProblemSolvingGroup@Miniforum,TakWaiAlanWONG(Markham,ON,Canada)andYUNGFai.
Note3n0(mod7).
Ifn0(mod7),thenn3≡1or–1(mod7).
So7isadivisorof3n+n3ifandonlyif–3n≡n3≡1(mod7)or–3n≡n3≡–1(mod7)ifandonlyif7isadivisorof3nn3+1.
Commendedsolvers:CHANKaLok(STFALeungKauKuiCollege),LAMShekKin(TWGHsLuiYunChoyMemorialCollege)andWONGKaiCheuk(CarmelDivineGraceFoundationSecondarySchool,Form6).
Problem243.
LetR+bethesetofallpositiverealnumbers.
Provethatthereisnofunctionf:R+→R+suchthat()()yxfyxfxf++≥)()()(2forarbitrarypositiverealnumbersxandy.
(Source:1998BulgarianMathOlympiad)Solution.
JoséLuisDíAZ-BARRERO,(UniversitatPolitècnicadeCatalunya,Barcelona,Spain).
Assumethereissuchafunction.
Werewritetheinequalityas.
)()()()(yxfyxfyxfxf+≥+Notetherightsideispositive.
Thisimpliesf(x)isastrictlydecreasing.
Firstweprovethatf(x)–f(x+1)≥1/2forx>0.
Fixx>0andchooseanaturalnumbernsuchthatn≥1/f(x+1).
Whenk=0,1,…,n1,weobtain)1()(nkxfnkxf+++.
211)(1)(nnnkxfnnkxf≥+++≥Addingtheaboveinequalities,wegetf(x)–f(x+1)≥1/2.
Letmbeapositiveintegersuchthatm≥2f(x).
Then∑=++=+miixfixfmxfxf1))()1(()()(≥m/2≥f(x).
Sof(x+m)≤0,acontradiction.
Commendedsolvers:ProblemSolvingGroup@Miniforum.
Problem244.
AninfinitesetSofcoplanarpointsisgiven,suchthateverythreeofthemarenotcollinearandeverytwoofthemarenotnearerthan1cmfromeachother.
DoesthereexistanydivisionofSintotwodisjointinfinitesubsetsRandBsuchthatinsideeverytrianglewithverticesinRisatleastonepointofBandinsideeverytrianglewithverticesinBisatleastonepointofRGiveaprooftoyouranswer.
(Source:2002AlbanianMathOlympiad)Solution.
(OfficialSolution)AssumethatsuchadivisionexistsandletM1beapointofR.
ThentakefourpointsM2,M3,M4,M5differentfromM1,whicharethenearestpointstoM1inR.
LetrbethelargestdistancebetweenM1andeachofthesefourpoints.
LetHbetheconvexhullofthesefivepoints.
ThentheinteriorofMathematicalExcalibur,Vol.
11,No.
1,Feb.
06-Mar.
06Page4HliesinsidethecircleofradiusrcenteredatM1,butallotherpointsofRisoutsideoronthecircle.
HencetheinteriorofHdoesnotcontainanyotherpointofR.
Belowwewillsaytwotrianglesaredisjointiftheirinteriorsdonotintersect.
Thereare3possiblecases:(a)Hisapentagon.
ThenHmaybedividedintothreedisjointtriangleswithverticesinR,eachofthemcontainingapointofBinside.
ThetrianglewiththesepointsofBasverticeswouldcontainanotherpointofR,whichwouldbeinH.
Thisisimpossible.
(b)Hisaquadrilateral.
ThenoneoftheMiisinsideHandtheotherMj,Mk,Ml,Mmareatitsvertices,sayclockwise.
ThefourdisjointtrianglesMiMjMk,MiMkMl,MiMlMm,MiMmMiinducefourpointsofB,whichcanbeusedtoformtwodisjointtriangleswithverticesinBwhichwouldcontaintwopointsinR.
SoHwouldthencontainanotherpointofRinside,otherthanMi,whichisimpossible.
(c)Hisatriangle.
ThenitcontainsinsideittwopointsMi,Mj.
OneofthethreedisjointtrianglesMiMkMl,MiMlMm,MiMmMkwillcontainMj.
ThenwecanbreakthattriangleintothreesmallertrianglesusingMj.
ThismakesfivedisjointtriangleswithverticesinR,eachhavingonepointofBinside.
WiththesefivepointsofB,threedisjointtriangleswithverticesinBcanbemadesothateachoneofthemhavingonepointofR.
ThenHcontainsanotherpointofR,differentfromM1,M2,M3,M4,M5,whichisimpossible.
Problem245.
ABCDisaconcavequadrilateralsuchthat∠BAD=∠ABC=∠CDA=45.
ProvethatAC=BD.
Solution.
CHANTszLung(HKUMathPGYear1),KWOKLoYan(CarmelDivineGraceFoundationSecondarySchool,Form6),ProblemSolvingGroup@Miniforum,WONGKaiCheuk(CarmelDivineGraceFoundationSecondarySchool,Form6),WONGManKit(CarmelDivineGraceFoundationSecondarySchool,Form6)andWONGTsunYu(St.
Mark'sSchool,Form6).
LetlineBCmeetADatE,then∠BEA=180∠ABC∠BAD=90.
NoteAEBandCEDare45-90-45triangles.
SoAE=BEandCE=DE.
ThenAECBED.
SoAC=BD.
Commendedsolvers:CHANKaLok(STFALeungKauKuiCollege),CHANPakWoon(HKUMathUGYear1),WONGKwokCheung(CarmelAlisonLamFoundationSecondarySchool,Form7)andYUENWahKong(St.
JoanofArcSecondarySchool).
OlympiadCorner(continuedfrompage1)Problem1.
(Cont.
)(c)thesumofalltermsofeverysequenceisatleast666Problem2.
LetObethecenterofthecircumcircleoftheacute-angledtriangleABC,forwhich∠CBAn,supposetheresultistrueforalldoublystochasticmatriceswithlessthanNpositiveentries.
LetDhaveexactlyNpositiveentries.
Forj=1,…,n,letWjbethesetofksuchthatDjk>0.
Weneedasystemofdistinctrepresentatives(SDR)forW1,…,Wn.
Togetthis,wechecktheconditioninHall'stheorem.
Foreverycollection,,,1mjjWWKnotemisthesumofallpositiveentriesincolumnj1,…,jmofD.
Thisislessthanorequaltothesumofallpositiveentriesinthoserowsthathaveatleastonepositiveentryamongcolumnj1,…,jm.
Thislattersumisthenumberofsuchrowsandisalsothenumberofelementsintheunionof.
,,1mjjWWKSotheconditioninHall'stheoremissatisfiedandthereisaSDRforW1,…,Wn.
Letσ(i)betherepresentativeinWi,thenσSn.
Letc(σ)betheminimumof.
,,)()1(1nnDDσσKIfc(σ)=1,thenDisapermutationmatrix.
Otherwise,letD'=(1–c(σ))–1(D–c(σ)M(σ)).
ThenD=c(σ)M(σ)+(1–c(σ))D'andD'isadoublestochasticmatrixwithatleastonelesspositiveentriesthanD.
SowemayapplythecaseslessthanNtoD'andthus,Dhastherequiredsum.