1TheAlibabaGlobalMathematicsCompetition(Hangzhou2018)consistsof3problems.Eachconsistsof3questions:a,b,andc.Thisdocumentincludesanswersforyourreference.Itisimportanttonotethattherearemultipleanswerstoeachquestion.Ifyousubmitteddiferentanswers,youmaystillgetpoints.Wetrytowritetheanswersratherthoroughly.Itdoesnotmeanyouranswersneedtobeasdetailed.Thisdocumentisneitherarubricnoragradingguide.Theauthorsoftheseanswersarenotthegraders.(correction11)Problem1.a.DuringtheAlibaba11.11ShoppingFestival,StoreAissues“5RMBof60RMB”stackablecoupons.“Stackable”meansthemultiplecouponscanbeappliedtoasingleorder.Forexample,anorderof120RMBatlistprice,canbereducedto110RMBbyapplyingtwosuchcoupons.StoreAispartofT.Tissuesa“60RMBof299RMB”coupon,limitedtooneperorder.Thiscouponappliestothelistpriceandisstackablewithanyindividualstorecoupons.Forexample,toaproductlistedat299RMBinaTstore,onepaysonly299RMB-(thestorediscountbasedon299RMB)-60RMB.Ifthetotallistpriceisslightlybelow299RMB,customersoftenadds?lleritem(s)(suchassocksortissues)fromotherTstorestoreach299RMBandthenapplythecoupon.XiaoMingwillbuya250RMBpairofheadphonesanda600RMBspeakersetfromTStoreA.XiaoMinghasunlimitedaccesstothetwotypesofcouponsdescribed.Whatistheleastamountthathemustpay?Answer:709RMB.Togetthisanswer,wehaveused?lleritemsfromotherstore(s).Theanswerwillbereducedto705RMBifthereare?lleritemssolelyfromStoreA(butthisislesslikelytoholdinpractice.)Below,weexplainthestepstoget709RBM.Belowwecomparebuyingbothitemsinoneorderandbuyingthemintwoseparateorders.Thelatterat709ischeaper.Buythetwoitemsinoneorder:The?nalcostis250(headphones’listprice)+600(speakerset’slistprice)-60(shoppingcartcoupon)=720.Buythetwoitemsseparately:Thetwoorderscost709,whichbreaksdowntothefollowingtwoorders:Theheadphonepaircosts250-4×+49(?lleritemstoreach299totallistprice)-60(shoppingcartcoupon)=219.(1)1changelog:“50RMBof299RMB”iscorrectedto“60RMBof299RMB”2Ifoneforgetstouse?lleritems,s/hewillpay250—20=230,whichis11more.Thespeakersetcosts—60(shoppingcartcoupon)=490.(2)Hencealltogether219+490=709RMB.b.YouplantoopenyourownTstore,called“StoreB,”sellingthesameheadphonesandspeakersetatthesamelistpricesasStoreAdoes.Yourstoresellsonlythesetwomodels.Youplantoissue“xRMBof99RMB”coupons,limitedtooneperorder,wherexisanintegergreaterthan0andsmallerthan99.(Forexample,thediscountforanorderof250RMBisxRMB,not2xRMB).TheT“60RMBof299RMB”couponcanbeappliedtopurchasesatstoreBandcanbestackedwithyour“xRMBof99RMB”coupon.WhatistheminimalnumberxsuchthatXiaoMingcanspendatleast1RMBlessoneitherthe250RMBpairoftheheadphonesorthe600RMBspeakerssetinyourStoreBthaninStoreA?WhatistheminimalnumberxsuchthatXiaoMingcanspendatleast1RMBlessforbuyingboththe250RMBpairoftheheadphonesandthe600RMBspeakerssetinyourStoreBthaninStoreA?Toclarify,thecomparisonisbetweenthecostswiththecouponsappliedoptimally.Answers:1stquestion:21ifusing?lleritemsfromotherstoresand25ifusing?lleritemsfromStoreA;2ndquestion:36forthe2ndquestionifusing?lleritemsfromotherstoresand38ifusing?lleritemsfromStoreA.Below,wegivethestepsassumeweuse?lleritemsfromotherstores.The1stquestion.Tobuyaheadphonepairinyourstore,onepays250—x+49(?ller)—60(shoppingcartcoupon)=239—x.Similarly,weget540—xforthespeakerset.Foryourstoretocostlessontheheadphonepair,xmustsatisfy239—x≤219(1),orx≥21.Foryourstoretocostlessonthespeakerpair,xmustsatisfy540—x≤490—1(2),orx≥51.Whenx=21,weensuretheheadphonepairtobecheaper,notthespeakersetthough.The2ndquestion.Tobuybothitemsinyourstore,itischeapertobuythemintwoseparateorderssincewecanapplythecoupontoeachordertogetatotaldiscountof2x.Thepartabovehastheformulasforthetwoorders:(239–x)and(540–x).Theirtotalmustbecheaperthan709,whichistheanswerinpart2.Thatis(239–x)+(540–x)≤709—1,orx≥35.5.Sincexisaninteger,wesetx=36forthisquestion2.c.Mathematicalmodelingofproductbundling.SupposethatthetotalcostsofItem1andItem2arec1andc2(includingproduction,storage,transportation,promotion,etc.),respectively.WhenacustomervisitstheTstore,s/heperceivesthevaluesoftheseitemsatS1andS2,respectively.WesupposethatS1andS2arerandomvariablesthatareindependentlyand uniformlydistributedontheintervals[0,u1]and[0,u2],respectively.Therearethreequestions. 2DuetodiferentunderstandingoftheChineseversion,both36and51canbetakenasthecorrectanswer,becausethere,onemayunderstandthatonemightnothavetobuybothitemsinyourstoreorbothitemsinstoreA.31.Whatisthevalueforp1,thepriceforItem1,thatmaximizestheexpectedpro?tforeachvisitingcustomer?Here,assumethatavisitingcustomerwillpurchaseonepieceofItem1ifS1≥p1,andifso,yourpro?tis(p1?c1).Pleaseprovideaformula.Similarly,whatisthevalueforp2thatmaximizestheexpectedpro?tforeachvisitingcustomer?Answer:optimalpricepandexpectedpro?trfori=1,2.Sincethestepsareidenticalfori=1,2,wedropiforbrevity.LetRbetherandomvariableofpro?t,whichdependsonS.Wecalculateitsexpectation:r=ES(R)=ES((p?c)δbuy)=ES((p?c)δp≤S)Alternatively,wecanobtainthesameexpectedpro?tdirectlyastheproductofpro?t,(p?c),andtheprobabilityofbuying,.Thefunctionr(p):=isaconcavequadraticfunction,soitsmaximumisattainedatthepointp?suchthatr/(p*)=0ifp*isontheintervalofitsallowedvalues,[0,u].Indeed,r/(p*)=0yieldsp?=c≤u(otherwise,p*=u,whichisatrivialcase).Withp*=,wegetr*=rii2.AssumewearegoingtosellabundleitemincludingoneunitofItem1andoneunitofItem2atpricep12.Thetotalcostofthisitemist(c1+c2),where0<t<1.Assumeavisitingcustomerwillpurchaseonepieceofthisbundleif(S1+S2)≥p12,andifso,yourpro?tisp12?t(c1+c2).Determinethepricep12tomaximizetheexpectedpro?tforeachvisitingcustomer.Pleaseprovideaformula.Answer:thepricep12thatmaximizestheexpectedreturnisNotethatpiscontinuouswithrespecttoc12,includingonetheboundarypointsofthreeintervals,soonecanincludeeachboundarypointineitherorbothoftheneighboringintervals.Alsonotethatthecalculationisnotunique.Studentscan?ndtherightanswerbydrawingapictureandusinggeometry.Nomatterwhichapproachisused,ittakesthefollowingthreestepstocomputep.Step1.De?nerandomvariableS12:=S1+S2.ComputethedistributionofS12,denotedbyp12.Thisisnotauniformdistribution.4Step2.Computetheexpectedpro?tasafunctionofS12,whichisForp121+u2],wehaveES12((p12?c12)δbuy)≤0aslongasc12≥0.Step3.Overeachoftheintervals,maximizetheexpectedpro?t.Thatisto?ndthepro?tmaximizerpwithineachoftheintervals.maximizer.Fromp≤u1,wegetc12≤abovepisthemaximizeroftwhichonedoyouchoose?IsonestrateAnswer:Neitherstrategyisalwaysbetterthantheother.Toestablishthisclaim,itbetterthantheother,andtheothershowingtheotherwayaround.TherearemanysuProblem2:a.Theattached?gureisanundirectedgraph.Thecirclednumbersrepresentthenodes,andthenumbersalongtheedgesaretheirlengths(symmetricalinbothdirections).C1C3AnAlibabaHemaXianshengcarrierstartsatpointAandwillpickupthreeordersfrommerchantsB1,B2,B3anddeliverthemtothreecustomersC1,C2,C3,respectively.Thecarrierdrivesascooterwithatrunkthatholdsatmosttwoordersatanytime.Alltheordershaveequalsize.FindtheshortesttravelroutethatstartsatAandendsatthelastdelivery.Tosimplifythisquestion,assumenowaitingtimeduringeachpickupanddelivery.Answer:Theshortesttraveldistanceis16,attainedbythecarriertakingthefollowingstops:A艸B2艸C2艸B1艸B3艸C3艸C1.Therearetwoslightlydiferentrouteswiththesamelengthof16:Route1:2(A)→6→7(B2)→8→11(C2)→8→3(B1)→4(B3)→15→14→13(C3)→12(C1);Route2:2(A)→6→7(B2)→10→11(C2)→8→3(B1)→4(B3)→15→14→13(C3)→12(C1).Eitherroutewillreceivethefullpoints.Enumeratingallthefullroutesandcomputingtheirlengthswouldbeexhaustive.However,thisproblemcanbesolvedwithoutacompleteenumerationbecausethegraphisaplanargraphandtheedgelengthsaresuchthatthetraveldirectionisalwayswith90degreesofthedestination.Thismeans,theshortestpathbetweenanytwonodesiseasyto?nd.Tosolvethisproblembyhand,onecan?rstguessagood(notnecessarilyoptimal)sequenceoutof{B1,C1,B2,C2,B3,C3}andcalculateitstraveldistance.Indeed,thereareseveralsequencesthatallleadtoadistanceof17.Ifyougetaslightlyhigherone,itis?ne.Thedistance56becomesanupperboundoftheshortestdistance.Then,startenumeratingallthesequencesfrom{B1,C1,B2,C2,B3,C3}buteliminatethoseonceapartoftheirtotaldistancereaches17.Whenyou?ndaroutewithdistance16,itbecomesthenewupperbound.Thisprocedureisb.Thisquestionisunrelatedtothegraphshowninparta;instead,weconsiderageneralgraphofmanynodesandedges.Supposethatthecarrierjustpickedupanorder(wecallittheoriginalorder)andwilltravelthroughtheedgese1,e2,...,eminthegraphtodeliverthisoriginalorder.Whens/hetravelsthroughanedgee,s/hemaypickupaneworderforthesamedestinationfromamerchantlocatedsomewhereonthisedge,atprobabilityPe∈[0,1].Suchprobabilitiescorrespondingtotheedgese1,e2,...,emareP1,P2,...,Pm.Weignoretheprobabilityoftwoormoresuchnewpickupsoneachedgeeastheytendtobeverysmall.Whatistheexpectednumberofneworder(s)forthesamedestinationthatthiscarriercanpickupoverthegivenroute(disregardingthetrunkcapacity)?Whatistheprobabilitythats/hepicksupatleastoneneworderforthesamedestinationoverthegivenroute?Answer:Forthe1stquestion,P1+P2+···+Pm.Letui∈{0,1}bethenumberofpickupoveredgeei,fori=1,...,m.WecangetouranswerfromE(u1+u2+···+um)=E(u1)+E(u2)+···+E(um)=P1+P2+···+Pm.Forthe2ndquestion,1—(1—P1)(1—P2)...(1—Pm).Here,(1—Pi)istheprobabilityofnopickupovereiand,bystatisticalindependence,(1—P1)(1—P2)...(1—Pm)isthatofnopickupovertheentireroute,so1minusthisproductistheprobabilityofpickingupatleastoneorder.Alternatively,onecanuseconditionalprobabilitytoobtaintherecursion:P1+(1—P1)Pr(atleastonenewpickupaftere1)=P1+(1—P1)(P2+(1—P2)Pr(atleastonenewpickupaftere2))==P1+(1—P1)(P2+(1—P2)(P3+...(Pm-1+(1—Pm-1)Pm)))).Thisrecursionisalsoarightanswer.Bothoftheaboveanswersarealsoequaltoc.Thisquestionisafollowupofpartb.Inthisquestion,wenolonger?xtherouteinpartbbut?ndonetomaximizethecarrier’spro?t.Supposethatthecarrierreceivesa?xedrewardofrforeachdeliveryandspendsl,whichequalsthetotallengthsoftheedgesthats/hetravelsfrompickuptodelivery.Intotal,s/hemakesapro?tofr—lonthisdelivery.(Wehavesetthecostfactoroftraveldistanceto1,forsimplicity.)Supposethatthecarrierjustpickeduptheoriginalorderandhasthisorderonly.Whatishis/heroptimalrouteassumingthescooter’strunkhasacapacityof2orders?Youshallconsiderboththetraveldistanceasacostandthepossibleadditionalpro?tofrforpickingupaneworder.Becauseanyneworderhasthesamedestination,itstravelcostisignored.Also,supposethat0≤Pe≤min{le/r,1},whereleisthelengthofedgeeandPeisde?nedinpartb.7Answer:Assume,withoutlossofgenerality,thereareTnodesandTisthedesti-nationnode.First,fromeverynodei,?ndtheshortestpathtoTanditsshortesttraveldistanceci(ifthereisatiebetweenmultiplepathswiththesamedistance,breakitarbitrarily.)Fori=T,wehavecT=0.Next,using{c1,c2,...,cT},computetheoptimalexpectedfuturerewardriateverynodei,usingthemaximizationformula(3)givenbelow.ForiT,letjibetheadjacentnodeofithatattainsthemaximum(again,ifthereisatie,breakitarbitrarily.)Thecarrier’sbestrouteisdecidedateachnodeasfollows:atnodei,ifthecarrierhasyettopickupanextraorder,traveltoji;ifthecarrierhaspickedupanextraorder,thenhis/hertrunkhasreachedthemaximumcapacity,sofollowtheshortestpathfromitoT.Notethattheaboverouteisnotpredeterminedbutdecidedasthecarriertravels.Inotherword,itisastrategyorpolicy.Itisbetterthanfollowinganypredeterminedroutebecausethebestwaydependsonwhetheranextrapickupismadeornot.Whenthecarrierisatanodeiandhasnotmadeasecondpickup,decidingwherethecarriershouldgousestheexpectationofthe“pro?ttogo”,whichfurtherdependsonbothpickupprobabilitiesandtraveldistancetoT.De?neriastheoptimalexpectedfuturepro?tatnodeibeforeanextrapickup.Fori=T,weletrT=r,whichisthe?xedreward.Supposewehavecalculatedrjfortheadjacentnodesofi.Ati,ifwetraveltotheadjacentnodej,thentheexpectedfuturepro?tbecomes:?(2r—cj)—l(i,j),ifapickupoccursover(i,j),happeningwithprobabilityP(i,j);?rj—l(i,j),ifapickupdoesnotoccursover(i,j),happeningwithprobability1—P(i,j),wherel(i,j)isthelengthofedge(i,j).ThemaximumoveralltheadjacentnodesisThisisknownastheBellmanequation.GivenrT=rand(3),wecancompute{ri}usingeitherdynamicprogramming,ormorespeci?-callyforgraphs,BellmanFord’salgorithmorDijkstra’salgorithm(seethejusti?cationbelow).TheyallstartfromrT=randiterativelydeterminetheelementsof{ri}.TheconditionPe≤le/r,orrPe≤le,avoidsthepresenceofany“positiverewardcycle”,whichifexistswouldgivethecarrierthemotivationtocyclearoundtoincreasehis/herexpectedrewarduntilanextraorderis?nallypickedup,whichisunrealistic.Notethat,Dijkstra’salgorithm,whichstudentstendtouseovertheotherchoices,requiresa“nonnegativeedgelength”condition.So,ifoneappliesittocompute{ri},theyshouldverifythatcondition.Forourproblem,thatistoshow(1—P(i,j))rj+P(i,j)(2r—cj)—l(i,j)≤rj.(4)UndertheproblemassumptionPe≤le/r,thisconditionindeedholds.Letusseewhy.SincethecarriercandonoworsethantravelingalongtheshortestpathtoT(ratherthanchoosinganodethatmaximizestheexpectedpro?t),wehaver—cj≤rj,8whichyieldsthesecondinequalityinP(i;j)r+(P(i;j)r-l(i;j))≤P(i;j)r≤P(i;j)(cj+rj);wherethe?rstinequalityfollowsfromtheproblemassumptionP(i;j)r≤l(i;j).Weget(4)bycombiningtheinequalitiesabove.9Problem3:a.ProfessorMahasformulatedndiferentbutequivalentstatementsA1,A2,...,An.Everysemester,headvisesastudenttoproveanimplicationAi?Aj,ij.Thisisthedissertationtopicofthisstudent.Everysemester,hehasonlyonestudent,andweassumethatthisstudent?nishesher/hisdissertationwithinthesemester.Nodissertationshouldbeadirectlogicalconsequenceofpreviouslygivenones.Forexample,ifAi?AjandAj?Akhavealreadybeenusedasdissertationtopics,ProfessorMacannotuseAi?Akasanewdissertationtopic,astheimpli-cationfollowsfromthepreviousdissertations.WhatisthemaximalnumberofstudentsthatProfessorMacanadvise?Answer:Wewill?rstconstructananswerwiththisisthebestpossibleanswer.Wealsopresentanalternativeconstructiveproofthatyields —1).Construction.First,(n—1)studentssequentiallyproveA1?Aifori=2,...,n.Then,(n—2)studentssequentiallyproveA2?Aifori=3,...,n.Continuethisuntil1studentprovesAn-1?An.NotethatallimplicationsprovensofararevalidtheseandhavetheformAi?Ajfori<j.Next,(n—1)studentssequentiallyproveAn?An-1,An-1?An-2,···,A2?A1,whicharealsovalidtheses.ThetotalnumberofthesesisLet—1).Proofofoptimality.ConsideragraphG=(N,E)withnodesN={1,2,...,n}anddirectededgesE={(i,j)|Ai?Ajhasbeenshown}.Completingathesis,i.e.,provinganimplication,meansaddinganedgetoE.De?neE,:={(i,j)|Ai?AjandAj?Aihavebeenshown}≤Ebethesetof“dualedges.”ThesubgraphG,=(N,E,)hasatmost2(n—1)directededges;otherwise,theremustbeacycleofdualedges,whichcontainsinvalidtheses.Ghasatmostn(n—1)/2pairsofnodes.Removethepairsofnodeswiththedualedges,andaswehaveargued,thereareatmost2(n—1)directededgesandthusatmost(n—1)suchpairs,leavinguswithn(n—1)/2—(n—1)=(n—2)(n—1)/2pairsofnodeswitheitherone-wayedgesornoedgeinbetween.Inotherwords,thereareatmost(n—2)(n—1)/2one-wayedges.Therefore,addingthemaximalnumbersofone-wayanddualedgesgivesusAnotherapproachthatisaconstructiveproof.ConsideragraphG=(N,E)withnodesN={A1,A2,...,An}anddirectededgesE={(Ai,Aj)|thestatementAi?Ajhasbeenshown}.CompletingathesisAi?Ajmeansaddingthedirectededge(Ai,Aj)toE.WesayAiimpliesAjandwriteitasAi艸AjifEcontainsapath(asuccessionofhead-to-tailconnectededges)fromAitoAj.WesayS≤Nisamaxequivalentclass(MEC)ifAi艸Aj,foralli,j∈S,andanylargerS,DSdoeshavethisproperty.Bythisde?nition,ifAi艸Ajandj∈S,thenwehaveAi艸Akforallk∈S;hence,wewritethisasAi艸S.Similarly,ifAi艸Ajforsomei∈S,wewriteS艸Aj.Also,ifS1,S2aretwodistinctMECsandAi艸Ajforsomei∈S1,j∈S2,thenwewriteS1艸S2.ForanyMECSandi∈/S,wedonothaveAi艸SandS艸AiduetothemaximalityofS.DependingonE,thesetNmaybepartitionedtothelargestMEC,Nitself,andatmostnindividualdistinctMECs,{1},{2},...,{n}.Eachthesismay,butnotnecessarily,jointwodistinctMECsintotheirunionMEC.EachthesiscannotjointhreeormoredistinctMECsintotheunionMEC.Therefore,ourproblemreducesto?ndingthemaximalsequenceofvalidthesesthatturnthenindividualMECs{1},{2},...,{n}intoanMECofsizen.Forintegerx>0,letf(x)bethemaximalnumberofsequentiallyvalidthesesthatgeneratesanMECofsizex,startingfromxindividualdistinctMECs.Clearly,f(1)=0.Foranyn≥2,onemustformanMECofsizenbyjoiningtwoMECsofsizesxandn-x,forsomex∈{1,...,n-1}.BeforethetwoMECsarejoined,thereareatmostx(n-x)same-wayedgesbetweenthem,andanopposite-wayedgecompletestheirjoining.Therefore,Startingfromf(1)=0,wecanusethisformulatocomputef(2),f(3),....CalculationyieldsForeachn,thetermthatattainsthemaximum(sayatx=xn)impliesanoptimalconstruction:giventwosubsetsofnodesofsizesxnandy-xn,?rstaddxn(y