SolvingRussianMathProblems Mostolympiadbooksbeginwithdefinitionsfollowedbytheoremsand proofsofimportantresultsbeforeproblemsaresolved.But,we'lljump right inwithaproblemthat,eventhoughitneedsnospecialmathresults,is stillbaffling. Matholympiadproblemsarebynaturealittledifferentthan theproblemsyousolveinyourclassroom.But,theydon'tnecessarily use additionalresultsasmuchasthinkingaboutthematadeeperlevel.And, no oneisthisbettermanifestedthanthe problemsintheRussianmathematicsolympiads. Onceyoulearnthestyleofsolvingthesetypesof problems,youwillfindthemquiteeasytosolve.
e. WhenyoufirstlookatRussianMathOlypmiadproblemsyouhavenoidea astohowtoevenbeginsolvingthem.Often,youcannotevenpinpointthe mathematicaltopicdoyouapplysettheory,algebraicequations,etc. Forexample,considerthefollowing: Let$\{a_1,a_2,\ldots,a_{10}\}$beastrictlyincreasingsequenceof positiveintegersnotexceeding45.Provethat thereexisttwodistinctpairssuchthatthedifferencesofthetwonumbers ineachpairarethesame.
Whattypeofproblemisthis?It'sclearlynotaquadraticequation.Isita combinatorialproblem?Doweapplysettheory?Ifso,whatproperties areapplicable? Thekeytofiguringoutasolutionistotakeadeepbreathandtakeastep back.Thefirstthingtorealizeisthattheproblemisprobablynottoo difficultotherwiseitwouldnotbeasked.It'slikelyit'sactuallyquite simplebutthewordingoftheproblemismaskingthesimplicity. Secondly,takeheartthatit'snotsometopicyoumayhavesleptthrough. Moreoftenthannot,it'ssomewellknownconceptthatisjustcouchedin awaythatyoumaynothavethoughtaboutintheseterms. Theverylackofinformationinthesetypesofproblemsactuallyisthekey tobeginformulatingasolutionplan.Afterall,thereisnotmuchelsetogo on.So,whateverisstatedintheproblemisallthatwehave.Wejust needtofindit.And,tofindthestartingpoint,readtheproblemslowly withoutworryingaboutwhatweneedtoprove.Writethebitsandpieces ofinformationinmathematicaltermsasyouencounterthem. So,thefirstbitofinformationisthatwehave10numberssuchthat: \begin{displaymath} a_1<a_2<\ldots<a_{10},\,\{i:a_i\leq45,\,i=1,2,\ldots10\} \end{displaymath} Doesn'tseemlikemuchhere.But,presson.There'ssometextabout thedifferencebetween2distinctpairsofthesenumbers.So,hereour mindstartsreelingdoweneedtoenumeratethepairs?Evenifwedid findthenumberofpairs,whichseemsatleastcountable,howdowego aboutenumeratingallpossibledifferences?Dowesubstitutedifferent
numbersinacontrolledmanner?Witheachnumberbeinglessthanor equalto45,that'sstillalotofpossibilities. But,firstthingsfirst.Let'sstartwithgettingahandleonthenumberof pairsandnotworryaboutanythingelseyet: $a_{10}a_9$,$a_{10}a_8$,$\ldots$,$a_2a_1$ Howmanypairsdowehave?Well,thatseemssimple:numberofways toselect2itemsfrom10: {10\choose2}=\frac{10!}{8!2!}=\frac{10\times9\times8!}{8!\times2} =\frac{90}{2}=45. Aha!The45seemsreasonablyclosetothe"eachnumbernot exceeding45"intheproblemstatement.So,thereseemstobesome connectionhere.Let'sexplorethisabit. Thereareonly45pairs,andsincethelargestofanypaircanbeno greaterthan45andthesmallestnolessthan1,thedifferenceofanypair isanintegerbetween1and44.But,sincethereare45pairs,bythe pigeonholeprinciple,therewillbeatleast2pairswhosedifferencewill bethesame. Alternateapproach: a_{10}=a_{10}a_9+a_9a_8+a_8a_7+\ldotsa_2a_1+a_1 Groupingthetermsasfollows: a_{10}=(a_{10}a_9)+(a_9a_8)+(a_8a_7)+\ldots(a_2a_1)+ a_1 a_{10}=a_1+\sum_{i=1}^{9}(a_{i+1}a_i)
Now,inthissum:$\sum_{i=1}^{9}(a_{i+1}a_i)$,the10smallestvalues thatcanbeaddedare$1,2,\ldots,9$sinceallthe$a_i$,for$1=1,2, \ldots,9$aredifferent,andhenceallthepairwisedifferencesare unique. Thus,$\sum_{i=1}^{9}(a_{i+1}a_i)\geq\sum_{i=1}^{9}i=\frac{10 \times9}{2}=45$. And, a_{10}\geqa_1+45\geq1+45=46. But,$a_{10}$cannotexceed46aspertheproblemcondition. Thus,for$a_{10}$tonotexceed45,allthepairwisedifferencescannot beuniquesothatwegetaminimumsumlessthan45.
