2018年阿里巴巴全球數(shù)學(xué)競(jìng)賽預(yù)選賽賽題及參考答案

1

TheAlibabaGlobalMathematicsCompetition(Hangzhou2018)consistsof3problems.Eachconsistsof3questions:a,b,andc.

Thisdocumentincludesanswersforyourreference.Itisimportanttonotethattherearemultipleanswerstoeachquestion.Ifyousubmitteddifferentanswers,youmaystillgetpoints.Wetrytowritetheanswersratherthoroughly.Itdoesnotmeanyouranswersneedtobeasdetailed.Thisdocumentisneitherarubricnoragradingguide.Theauthorsoftheseanswersarenotthegraders.

(correction11)

Problem1.

DuringtheAlibaba11.11ShoppingFestival,StoreAissues“5RMBoff60RMB”stackablecoupons.“Stackable”meansthemultiplecouponscanbeappliedtoasingleorder.Forexample,anorderof120RMBatlistprice,canbereducedto110RMBbyapplyingtwosuchcoupons.

StoreAispartofT.Tissuesa“60RMBoff299RMB”coupon,limitedtooneperorder.Thiscouponappliestothelistpriceandisstackablewithanyindividualstorecoupons.Forexample,toaproductlistedat299RMBinaTstore,onepaysonly299RMB-(thestorediscountbasedon299RMB)-60RMB.Ifthetotallistpriceisslightlybelow299RMB,customersoftenaddsfilleritem(s)(suchassocksortissues)fromotherTstorestoreach299RMBandthenapplythecoupon.

XiaoMingwillbuya250RMBpairofheadphonesanda600RMBspeakersetfromTStoreA.XiaoMinghasunlimitedaccesstothetwotypesofcouponsdescribed.Whatistheleastamountthathemustpay?

Answer:709RMB.Togetthisanswer,wehaveusedfilleritemsfromotherstore(s).Theanswerwillbereducedto705RMBiftherearefilleritemssolelyfromStoreA(butthisislesslikelytoholdinpractice.)Below,weexplainthestepstoget709RBM.

Belowwecomparebuyingbothitemsinoneorderandbuyingthemintwoseparateorders.Thelatterat709ischeaper.

Buythetwoitemsinoneorder:Thefinalcostis

250(headphones’listprice)+600(speakerset’slistprice)

60

?14×5apply(l250+600J=14“5-off-60”storecoupons)

?60(shoppingcartcoupon)

=720.

Buythetwoitemsseparately:Thetwoorderscost709,whichbreaksdowntothefollowingtwoorders:Theheadphonepaircosts

60

250?4×5(applyl250」=4storecoupons)

+49(filleritemstoreach299totallistprice)?60(shoppingcartcoupon)

=219. (1)

1changelog:“50RMBoff299RMB”iscorrectedto“60RMBoff299RMB”

PAGE

10

Ifoneforgetstousefilleritems,s/hewillpay250?20=230,whichis11more.Thespeakersetcosts

60

600?10×5(applyl600」=10storecoupons)

?60(shoppingcartcoupon)

=490. (2)

Hencealltogether219+490=709RMB.

YouplantoopenyourownTstore,called“StoreB,”sellingthesameheadphonesandspeakersetatthesamelistpricesasStoreAdoes.Yourstoresellsonlythesetwomodels.

Youplantoissue“xRMBoff99RMB”coupons,limitedtooneperorder,wherexisanintegergreaterthan0andsmallerthan99.(Forexample,thediscountforanorderof250RMBisxRMB,not2xRMB).TheT“60RMBoff299RMB”couponcanbeappliedtopurchasesatstoreBandcanbestackedwithyour“xRMBoff99RMB”coupon.

WhatistheminimalnumberxsuchthatXiaoMingcanspendatleast1RMBlessoneitherthe250RMBpairoftheheadphonesorthe600RMBspeakerssetinyourStoreBthaninStoreA?

WhatistheminimalnumberxsuchthatXiaoMingcanspendatleast1RMBlessforbuyingboththe250RMBpairoftheheadphonesandthe600RMBspeakerssetinyourStoreBthaninStoreA?

Toclarify,thecomparisonisbetweenthecostswiththecouponsappliedoptimally.

Answers:1stquestion:21ifusingfilleritemsfromotherstoresand25ifusingfilleritemsfromStoreA;2ndquestion:36forthe2ndquestionifusingfilleritemsfromotherstoresand38ifusingfilleritemsfromStoreA.Below,wegivethestepsassumeweusefilleritemsfromotherstores.

The1stquestion.Tobuyaheadphonepairinyourstore,onepays250?x+49(filler)?

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.

2

Thepartabovehastheformulasforthetwoorders:(239–x)and(540–x).Theirtotalmustbecheaperthan709,whichistheanswerinpart2.Thatis(239–x)+(540–x)≤709?1,orx≥35.5.Sincexisaninteger,wesetx=36forthisquestion.

Mathematicalmodelingofproductbundling.SupposethatthetotalcostsofItem1andItem2arec1andc2(includingproduction,storage,transportation,promotion,etc.),respectively.WhenacustomervisitstheTstore,s/heperceivesthevaluesoftheseitemsatS1andS2,respectively.WesupposethatS1andS2arerandomvariablesthatareindependentlyanduniformlydistributedontheintervals[0,u1]and[0,u2],respectively.Therearethreequestions.

2DuetodifferentunderstandingoftheChineseversion,both36and51canbetakenasthecorrectanswer,becausethere,onemayunderstandthatonemightnothavetobuybothitemsinyourstoreorbothitemsinstoreA.

Whatisthevalueforp1,thepriceforItem1,thatmaximizestheexpectedprofitforeachvisitingcustomer?Here,assumethatavisitingcustomerwillpurchaseonepieceofItem1ifS1≥p1,andifso,yourprofitis(p1?c1).Pleaseprovideaformula.Similarly,whatisthevalueforp2thatmaximizestheexpectedprofitforeachvisitingcustomer?

2

Answer:optimalpricep?=ui+ciandexpectedprofitr?=(ui?ci)

fori=1,2.

i 2 i 4ui

Sincethestepsareidenticalfori=1,2,wedropiforbrevity.LetRbetherandomvariable

ofprofit,whichdependsonS.Wecalculateitsexpectation:

r=ES(R)=ES((p?c)δbuy）

r

=ES((p?c)δp≤S）

u 1

0

= (p?c)δp≤s·uds

1

ss=u

=(p?c)us=p

=(p?c)(u?p).u

u

Alternatively,wecanobtainthesameexpectedprofitdirectlyastheproductofprofit,(p?c),andtheprobabilityofbuying,u?p.

u

2

Thefunctionr(p):=(p?c)(u?p)isaconcavequadraticfunction,soitsmaximumisattainedatthepointp?suchthatrt(p?)=0ifp?isontheintervalofitsallowedvalues,[0,u].Indeed,rt(p?)=0yieldsp?=u+c,whichisthemaximizerifc≤u(otherwise,p?=u,

whichisatrivialcase).

Withp?=u+c,wegetr?=r(p?)=(u?c)2.

2 4u

?

AssumewearegoingtosellabundleitemincludingoneunitofItem1andoneunitofItem2atpricep12.Thetotalcostofthisitemist(c1+c2),where0<t<1.Assumeavisitingcustomerwillpurchaseonepieceofthisbundleif(S1+S2)≥p12,andifso,yourprofitisp12t(c1+c2).Determinethepricep12tomaximizetheexpectedprofitforeachvisitingcustomer.Pleaseprovideaformula.

Answer:thepricep12thatmaximizestheexpectedreturnis

3

12

2

1(c12+?c2+6u1u2）,c12∈[0,3u1?u2]

12

4

2

2

p?=

1(u1+2u2+2c12）, c12∈[3u1?u2,u2?1u1]

3

2

1(u1+u2+2c12), c12∈[u2?1u1,u1+u2].

12

Notethatp?iscontinuouswithrespecttoc12,includingonetheboundarypointsofthree

intervals,soonecanincludeeachboundarypointineitherorbothoftheneighboringintervals.

Alsonotethatthecalculationisnotunique.Studentscanfindtherightanswerbydrawingapictureandusinggeometry.

12

Nomatterwhichapproachisused,ittakesthefollowingthreestepstocomputep?.

Step1.DefinerandomvariableS12:=S1+S2.ComputethedistributionofS12,denotedbyp12.Thisisnotauniformdistribution.

ru1+u2

su1u2

, s∈[0,u1]

p12(s):=Pr(S=s)=

1

u2

p1(z?y)p2(y)dy=···= , s∈[u1,u2]

u1u2

2

1

2

0 u1+u2?s,s∈[u,u

+u].

Step2.ComputetheexpectedprofitasafunctionofS12,whichis

ES12

((p12?c12)δbuy）=

u1s

(r

+

uu

u21

r

+

u

u1+u2u1+u2?s

r \

uu

(p12?c12)δp12≤s12ds12

0 12 u1 2 u2 12

12

2u1u2

12

1

1?p2, p ∈[0,u]

u2

2u2

=···=(p12?c12)×

1?p12+u1,p12∈[u1,u2]

2u1u2

12

2

1

2

(u1+u2?p12)2, p

∈[u,u

+u].

( ）

Forp12/∈[0,u1+u2],wehaveES12(p12?c12)δbuy≤0aslongasc12≥0.

Step3.Overeachoftheintervals,maximizetheexpectedprofit.Thatistofindtheprofit

12

maximizerp?withineachoftheintervals.

p2

2u1u2

Forp12∈[0,u1],settingthederivativeof(p12?c12)(1?12)to0yields

12

3

12

12

p?=1(c

+?c2

+6uu）.

12

1

2

Drawthecurveorcheckthesecondderivative,anditiseasytoseetheabovep?

isa

12

3

maximizer.Fromp?≤u1,wegetc12≤u1?u2,whichistheconditionunderwhichthe

2

12

abovep?isthemaximizeroftheexpectedprofit.

12

Usingsimilarsteps,weobtainedp?

intheothertwocasesandtheircorrespondingintervals

ofc12.

IfyoumustchoosebetweensellingItems1and2separatelyandsellingtheminabundle,whichonedoyouchoose?Isonestrategyalwaysbetterthantheother?Why?

Answer:Neitherstrategyisalwaysbetterthantheother.

Toestablishthisclaim,itissufficienttouseapairofexamples,oneshowingonestrategybetterthantheother,andtheothershowingtheotherwayaround.Therearemanysuchexamples,sowedonotspecifyone.

Problem2:

Theattachedfigureisanundirectedgraph.Thecirclednumbersrepresentthenodes,andthenumbersalongtheedgesaretheirlengths(symmetricalinbothdirections).

1

1

2

2

3

1

4

1

2

2

5

1

6

1

B2

7

1

8

1

1

1

3

9

3

10

1

11C2

2

2

1

12

2

13

1

14

1

15

A B1 B3

C1 C3

AnAlibabaHemaXianshengcarrierstartsatpointAandwillpickupthreeordersfrommerchantsB1,B2,B3anddeliverthemtothreecustomersC1,C2,C3,respectively.Thecarrierdrivesascooterwithatrunkthatholdsatmosttwoordersatanytime.Alltheordershaveequalsize.

FindtheshortesttravelroutethatstartsatAandendsatthelastdelivery.Tosimplifythisquestion,assumenowaitingtimeduringeachpickupanddelivery.

Answer:Theshortesttraveldistanceis16,attainedbythecarriertakingthefollowingstops:

A-v--B2-v--C2-v--B1-v--B3-v--C3-v--C1.

Therearetwoslightlydifferentrouteswiththesamelengthof16:

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,theshortestpathbetweenanytwonodesiseasytofind.

{ }

Tosolvethisproblembyhand,onecanfirstguessagood(notnecessarilyoptimal)sequenceoutofB1,C1,B2,C2,B3,C3andcalculateitstraveldistance.Indeed,thereareseveralsequencesthatallleadtoadistanceof17.Ifyougetaslightlyhigherone,itisfine.Thedistance

{ }

becomesanupperboundoftheshortestdistance.Then,startenumeratingallthesequencesfromB1,C1,B2,C2,B3,C3buteliminatethoseonceapartoftheirtotaldistancereaches17.Whenyoufindaroutewithdistance16,itbecomesthenewupperbound.Thisprocedureiscalledbranchandbound.

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.Wecangetouranswerfrom

E(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,(1P1)(1P2)...(1Pm)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.

Bothoftheaboveanswersarealsoequalto

m

kX=1

k+1

(?1)

X

distincti1,...,ik∈{1,...,m}

Pi1Pi2

...Pi.

k

?

Thisquestionisafollowupofpartb.Inthisquestion,wenolongerfixtherouteinpartbbutfindonetomaximizethecarrier’sprofit.Supposethatthecarrierreceivesafixedrewardofrforeachdeliveryandspends￡,whichequalsthetotallengthsoftheedgesthats/hetravelsfrompickuptodelivery.Intotal,s/hemakesaprofitofr￡onthisdelivery.(Wehavesetthecostfactoroftraveldistanceto1,forsimplicity.)

Supposethatthecarrierjustpickeduptheoriginalorderandhasthisorderonly.Whatishis/heroptimalrouteassumingthescooter’strunkhasacapacityof2orders?Youshallconsiderboththetraveldistanceasacostandthepossibleadditionalprofitofrforpickingupaneworder.Becauseanyneworderhasthesamedestination,itstravelcostisignored.Also,supposethat0≤Pe≤min{￡e/r,1},where￡eisthelengthofedgeeandPeisdefinedinpartb.

Answer:Assume,withoutlossofgenerality,thereareTnodesandTisthedesti-nationnode.First,fromeverynodei,findtheshortestpathtoTanditsshortesttraveldistanceci(ifthereisatiebetweenmultiplepathswiththesamedistance,breakitarbitrarily.)Fori=T,wehavecT=0.

/

Next,using{c1,c2,...,cT},computetheoptimalexpectedfuturerewardriateverynodei,usingthemaximizationformula(3)givenbelow.Fori=T,letjibetheadjacentnodeofithatattainsthemaximum(again,ifthereisatie,breakitarbitrarily.)

Thecarrier’sbestrouteisdecidedateachnodeasfollows:atnodei,ifthecarrierhasyettopickupanextraorder,traveltoji;ifthecarrierhaspickedupanextraorder,thenhis/hertrunkhasreachedthemaximumcapacity,sofollowtheshortestpathfromitoT.

Notethattheaboverouteisnotpredeterminedbutdecidedasthecarriertravels.Inotherword,itisastrategyorpolicy.Itisbetterthanfollowinganypredeterminedroutebecausethebestwaydependsonwhetheranextrapickupismadeornot.

Whenthecarrierisatanodeiandhasnotmadeasecondpickup,decidingwherethecarriershouldgousestheexpectationofthe“profittogo”,whichfurtherdependsonbothpickupprobabilitiesandtraveldistancetoT.

Defineriastheoptimalexpectedfutureprofitatnodeibeforeanextrapickup.Fori=T,weletrT=r,whichisthefixedreward.Supposewehavecalculatedrjfortheadjacentnodesofi.Ati,ifwetraveltotheadjacentnodej,thentheexpectedfutureprofitbecomes:

(2r?cj)?￡(i,j),ifapickupoccursover(i,j),happeningwithprobabilityP(i,j);

rj?￡(i,j),ifapickupdoesnotoccursover(i,j),happeningwithprobability1?P(i,j),where￡(i,j)isthelengthofedge(i,j).Themaximumoveralltheadjacentnodesis

ri= max

jisadjacenttoi

= max

jisadjacenttoi

{P(i,j)((2r?cj)?￡(i,j))+(1?P(i,j))(rj?￡(i,j))}

{(1?P(i,j))rj+P(i,j)(2r?cj)?￡(i,j)}. (3)

ThisisknownastheBellmanequation.

{}

GivenrT=rand(3),wecancomputeriusingeitherdynamicprogramming,ormorespecifi-callyforgraphs,BellmanFord’salgorithmorDijkstra’salgorithm(seethejustificationbelow).TheyallstartfromrT=randiterativelydeterminetheelementsof{ri}.

≤ ≤

TheconditionPe￡e/r,orrPe￡e,avoidsthepresenceofany“positiverewardcycle”,whichifexistswouldgivethecarrierthemotivationtocyclearoundtoincreasehis/herexpectedrewarduntilanextraorderisfinallypickedup,whichisunrealistic.

{}

Notethat,Dijkstra’salgorithm,whichstudentstendtouseovertheotherchoices,requiresa“nonnegativeedgelength”condition.So,ifoneappliesittocomputeri,theyshouldverifythatcondition.Forourproblem,thatistoshow

(1?P(i,j))rj+P(i,j)(2r?cj)?￡(i,j)≤rj. (4)

≤

UndertheproblemassumptionPe￡e/r,thisconditionindeedholds.Letusseewhy.SincethecarriercandonoworsethantravelingalongtheshortestpathtoT(ratherthanchoosinganodethatmaximizestheexpectedprofit),wehave

r?cj≤rj,

whichyieldsthesecondinequalityin

P(i,j)r+(P(i,j)r?￡(i,j))≤P(i,j)r≤P(i,j)(cj+rj),

≤

wherethefirstinequalityfollowsfromtheproblemassumptionP(i,j)r ￡(i,j).Weget(4)bycombiningtheinequalitiesabove.

Problem3:

?

? /

ProfessorMahasformulatedndifferentbutequivalentstatementsA1,A2,...,An.Everysemester,headvisesastudenttoproveanimplicationAi Aj,i=j.Thisisthedissertationtopicofthisstudent.Everysemester,hehasonlyonestudent,andweassumethatthisstudentfinishesher/hisdissertationwithinthesemester.Nodissertationshouldbeadirectlogicalconsequenceofpreviouslygivenones.Forexample,ifAi?AjandAj?Akhavealreadybeenusedasdissertationtopics,ProfessorMacannotuseAi Akasanewdissertationtopic,astheimpli-cationfollowsfromthepreviousdissertations.WhatisthemaximalnumberofstudentsthatProfessorMacanadvise?

2

?

2

Answer:Wewillfirstconstructananswerwith1(n+2)(n1)students.Then,wewillshowthisisthebestpossibleanswer.Wealsopresentanalternativeconstructiveproofthatyields1(n+2)(n?1).

? ? ? ··· ?

Construction.First,(n?1)studentssequentiallyproveA1?Aifori=2,...,n.Then,(n?2)studentssequentiallyproveA2?Aifori=3,...,n.Continuethisuntil1studentprovesAn?1?An.NotethatallimplicationsprovensofararevalidtheseandhavetheformAi?Ajfori<j.Next,(n1)studentssequentiallyproveAnAn?1,An?1An?2,,A2A1,whicharealsovalidtheses.Thetotalnumberofthesesis

((n?1)+(n?2)+···+1）+(n?1)=1n(n?1)+(n?1)=1(n+2)(n?1).

2 2

2

Letf(k):=1(k+2)(k?1).

{ | ? }

Proofofoptimality.ConsideragraphG=(N,E)withnodesN={1,2,...,n}anddirectededgesE=(i,j)AiAjhasbeenshown.Completingathesis,i.e.,provinganimplication,meansaddinganedgetoE.

?

{ | ? ? }?

DefineEt:=(i,j)AiAjandAjAihavebeenshownEbethesetof“dualedges.”ThesubgraphGt=(N,Et)hasatmost2(n1)directededges;otherwise,theremustbeacycleofdualedges,whichcontainsinvalidtheses.

? ?

? ? ? ? ?

? ?

?

Ghasatmostn(n1)/2pairsofnodes.Removethepairsofnodeswiththedualedges,andaswehaveargued,thereareatmost2(n1)directededgesandthusatmost(n1)suchpairs,leavinguswithn(n1)/2(n1)=(n2)(n1)/2pairsofnodeswitheitherone-wayedgesornoedgeinbetween.Inotherwords,thereareatmost(n2)(n1)/2one-wayedges.Therefore,addingthemaximalnumbersofone-wayanddualedgesgivesus

1

(n?2)(n?1)/2+2(n?1)=2(n+2)(n?1)=f(n).

Anotherapproachthatisaconstructiveproof.ConsideragraphG=(N,E)withnodes

N={A1,A2,...,An}anddirectededgesE={(Ai,Aj)|thestatementAi?Ajhasbeenshown}.CompletingathesisAi?Ajmeansaddingthedirectededge(Ai,Aj)toE.

WesayAiimpliesAjandwriteitasAi-v--AjifEcontainsapath(asuccessionofhead-to-tailconnectededges)fromAitoAj.

WesayS?Nisamaxequivalentclass(MEC)ifAi-v--Aj,foralli,j∈S,andanylargerSt?Sdoeshavethisproperty.Bythisdefinition,ifAi-v--Ajandj∈S,thenwehaveAi-v--Akforallk∈S;hence,wewritethisasAi-v--S.Similarly,ifAi-v--Ajforsomei∈S,wewrite

S-v--Aj.Also,ifS1,S2aretwodistinctMECsandAi-v--Ajforsomei∈S1,j∈S2,thenwewriteS1-v--S2.

{}{} {}

ForanyMECSandi/∈S,wedonothaveAi-v--SandS-v--AiduetothemaximalityofS.DependingonE,thesetNmaybepartitionedtothelargestMEC,Nitself,andatmost

nindividualdistinctMECs,1,2,...,n.Eachthesismay,butnotnecessarily,jointwo

distinctMECsintotheirunionMEC.EachthesiscannotjointhreeormoredistinctMECsintotheunionMEC.

Therefore,ourproblemreducestofindingthemaximalsequenceofvalidthesesthatturnthen

individualMECs{1},{2},...,{n}intoanMECofsizen.

Forintegerx>0,letf(x)bethemaximalnumberofsequentiallyvalidthesesthatgeneratesanMECofsizex,startingfromxindividualdistinctMECs.Clearly,f(1)=0.

∈{ ?} ?

≥ ?

Foranyn2,onemustformanMECofsizenbyjoiningtwoMECsofsizesxandnx,forsomex1,...,n1.BeforethetwoMECsarejoined,thereareatmostx(nx)same-wayedgesbetweenthem,andanopposite-wayedgecompletestheirjoining.Therefore,

f(n)= max

x∈{1,...,n?1}

{f(x)+f(n?x)+x(n?x)+1}.

Startingfromf(1)=0,wecanusethisformulatocomputef(2),f(3),Calculationyields

1

f(n)=2(n+2)(n?1).

? ?

Foreachn,thetermthatattainsthemaximum(s