2010首届丘成桐大学生数学竞赛个人赛解答

S.-T.YauCollegeStudentMathematicsContests2010AnalysisandDi®erentialEquationsIndividualSolution1.a)Letxk,k=1;:::;nberealnumbersfromtheinterval(0;¼)andde¯nex=nXi=1xin.ShowthatnYk=1sinxkxk·µsinxx¶n:b)FromZ10e¡x2dx=p¼2;calculatetheintegralR10sin(x2)dx:Proof.a)Applyinequalityofconvexfunctionstof(x)=log(sin(x)=x).¤2.Letf:R!Rbeanyfunction.ProvethatthesetofpointsxinRwherefiscontinuousisacountableintersectionofopensets.Proof.Usethede¯nitionofacontinuousfunction.¤3.Considertheequation_x=¡x+f(t;x);wherejf(t;x)j·Á(t)jxjforall(t;x)2R£R,R1Á(t)dt1.Provethateverysolutionapproacheszeroast!1.4.Findaharmonicfunctionfontherighthalf-planesuchthatwhenapproachinganypointinthepositivehalfofthey-axis,thefunctionhaslimit1,whilewhenapproachinganypointinthenegativehalfofthey-axis,thefunctionhaslimit¡1.Proof.Useconformalmappingtomaptherighthalfplanetotheunitdisk,thenapplyPoissonformulaofharmonicfunctionwithboundaryvalueovertheunitcircle.¤125.LetK(x;y)2C([0;1]£[0;1]).Forallf2C[0;1],thespaceofcontinuousfunctionson[0;1],de¯neafunctionTf(x)=Z10K(x;y)f(y)dyProvethatTf2C([0;1]).Moreover­=fTfjjjfjjsup·1gisprecom-pactinC([0;1]),i.e.everysequencein­hasaconvergingsubsequence,herejjfjjsup=supfjf(x)jjx2[0;1]g.Proof.FirstusepolynomialstoapproximateKintheL1norm,thenuseuniformcontinuitypropertyofapolynomialfunctiontoshowthatTfnareuniformlycontinuous.¤6.ProvethePoissonsummationformula:1Xn=¡1f(x+2¼n)=12¼1X¡1^f(k)eikxforallfoffunctionsoverRintheSchwartzspace:S=ff:(1+x2)mjf(n)(x)j·Cm;n;m;n¸0gwhere^f(»)=RRf(x)e¡ix»dx:S.-T.YauCollegeStudentMathematicsContests2010AppliedMath.,ComputationalMath.,ProbabilityandStatisticsIndividualSolution1.LetZ1;¢¢¢;Znbei.i.d.randomvariableswithZi»N(¹;¾2).FindE(nXi=1ZijZ1¡Z2+Z3):2.LetX1;¢¢¢;Xnbepairwiseindependent.Further,assumethatEXi=1+i¡1andthatmax1·i·nEjXij1+²1forsome²0.Showthat1nnXi=1XiP¡!1:3.LetZ1;¢¢¢;Z6bei.i.d.randomvariableswithZi»N(0;1).SetU2=(Z1Z2+Z3Z4+Z5Z6)2Z22+Z24+Z26;V2=U2(Z22+Z24)U2+Z26:FindandidentifythedensitiesofU2andV2.4.Supposethatthreecharacteristicsinalargepropulationcanbeob-servedaccordingtothefollowingfrequenciesp1=µ3;p2=3µ(1¡µ);p3=(1¡µ)3;whereµ2(0;1).LetNj;j=1;2;3betheobservedfrequenciesofcharacteristicjinarandomsampleofsizen.(a)Constructtheapproximatelevel(1¡®)maximumlikelihoodcon¯dencesetforµ.(b)Derivetheasymptoticdistributionforthefrequencysubstitutionestimator^µ2=1¡(N3=n)1=3.5.(1)SupposeS=·¾uT0Sc¸;T=·¿vT0Tc¸;b=·¯bc¸;where¾,¿and¯arescalars,ScandTcaren-by-nmatrices,andbcisann-vector.Showthatifthereexistsavectorxcsuchthat(ScTc¡¸I)xc=bc12andwc=Tcxcisavailable,thenx=·°xc¸;°=¯¡¾vTxc¡uTwc¾¿¡¸solves(ST¡¸I)x=b.(2)Henceorotherwise,deriveanO(n2)algorithmforsolvingthelinearsystem(U1U2¡¸I)x=bwhereU1andU2aren-by-nuppertriangularmatrices,and(U1U2¡¸I)isnonsingular.PleasewritedownyouralgorithmandprovethatitisindeedofO(n2)complexity.(3)Henceorotherwise,deriveanO(pn2)algorithmforsolvingthelinearsystem(U1U2¢¢¢Up¡¸I)x=bwherefUigpi=1arealln-by-nuppertriangularmatrices,and(U1U2¢¢¢Up¡¸I)isnon-singular.PleasewritedownyouralgorithmandprovethatitisindeedofO(pn2)complexity.Proof.(a)IfScTc¡¸Iisnonsingular,itmeansdet(ScTc¡¸I)6=0,orinotherwords,¸isnottheeigenvalueofScTc,thenthereexistsavectorxc=(ScTc¡¸I)¡1bcwhichsatis¯es(ScTc¡¸I)xc=bc,andwehave(ST¡¸I)x=µ·¾uT0Sc¸·¿vT0Tc¸¡·¸00¸I¸¶·°xc¸=·¾¿¡¸¾vT+uTTc0ScTc¡¸I¸24¯¡¾vTxc¡uTwc¾¿¡¸xc35=·¯bc¸=b:(b)Denotethe(i;j)thentryofU1andU2byu(1)ijandu(2)ijrespectively.Letxiandbibetheithcomponentofthevectorsxandbrespectively.Thepreviouspart(a)inspiresusto¯ndthecomponentsofthesolutionstepbystepinabackwardmanner,i.e.,westartfromxn,andthen¯ndxn¡1;:::;x1.Notethatthelastcomponentxncanbeexplicitlyfoundbyxn=bn=(u(1)nnu(2)nn¡¸);andfurthermoreweletwn=u(2)nnxn.Supposewehavealreadyobtainedxk+1;:::;xnandletx(k+1)=[xk+1;:::;xn]T.Thenwegetw(k+1)=[wk+1;:::;wn]T=U(k+1)2x(k+1).Atthecurrentstage,wesymbolizethelowerright(n¡k+1)-by-(n¡k+1)submatricesofU1andU2byU(k)1=u(1)kk(v(k)1)T0U(k+1)1#andU(k)2=u(2)kk(v(k)2)T0U(k+1)2#;3wherev(k)1andv(k)2areRn¡kvectors.Thereforewehavexk=bk¡u(1)kk(v(k)2)Tx(k+1)¡(v(k)1)Tw(k+1)u(1)kku(2)kk¡¸andwk=u(2)kkxk+(v(k)2)Tx(k+1):Sincexkandwkonlyrequirecalculatingcertaininnerproductsofsizesmallerthann,thecomputationalcostisofO(n)complexity.ThereforecollectingallncomponentsofthesolutionxrequiresO(n2)operations.(c)Thenotationsinthispartareanalogousto(b).We¯rstgener-alizetheresultin(a)totheproductofpmatrices,duringwhichweconcludethatwecanstill¯ndthecomponentsofthesolutionstepbystepinabackwardmanner.Supposewehavealreadyobtainedxk+1;:::;xnandletx(k+1)=[xk+1;:::;xn]T.Thenweupdatexk=bk¡(v(1)k)Tw(p¡1;k+1)¡Pp¡1j=1³Qji=1u(i)kk(v(j+1)k)Tw(p¡1¡j;k+1)´u(1)kku(2)kk¢¢¢u(p)kk¡¸;wherew(i;k+1)=U(k+1)p¡i+1¢¢¢U(k+1)px(k+1);i=1;2;:::;p¡1areob-tainedinthepreviousstep.Onecan¯ndoutthatpinnerprod-uctsarecalculatedinordertogetxk.Nextweonlyneedtoupdatew(i;k)=U(k)p¡i+1¢¢¢U(k)px(k);i=1;2;:::;p¡1byperformingp¡1in-nerproductsofsizesmallerthann.ThereforethetotaloperationcosttoderiveasinglecomponentofthesolutionxisofO(pn).Incon-clusion,collectingallncomponentsofthesolutionxrequiresO(pn2)operations.¤6.(1)LetA2Rm£n,i.e.Aisanm-by