2018年阿里巴巴全球数学竞赛预选赛赛题及参考答案

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