历届美国数学建模竞赛赛题(2001-2009)

2001MCMA:ChoosingaBicycleWheel

Cyclistshavedifferenttypesofwheelstheycanuseontheirbicycles.Thetwobasictypesofwheelsarethoseconstructedusingwirespokesandthoseconstructedofasoliddisk(seeFigure1)Thespokedwheelsarelighter,butthesolidwheelsaremoreaerodynamic.Asolidwheelisneverusedonthefrontforaroadracebutcanbeusedontherearofthebike.

Professionalcyclistslookataracecourseandmakeaneducatedguessastowhatkindofwheelsshouldbeused.Thedecisionisbasedonthenumberandsteepnessofthehills,theweather,windspeed,thecompetition,andotherconsiderations.Thedirectorsportifofyourfavoriteteamwouldliketohaveabettersysteminplaceandhasaskedyourteamforinformationtohelpdeterminewhatkindofwheelshouldbeusedforagivencourse.

Figure1:Asolidwheelisshownontheleftandaspokedwheelisshownontheright.

Thedirectorsportifneedsspecificinformationtohelpmakeadecisionandhasaskedyourteamtoaccomplishthetaskslistedbelow.Foreachofthetasksassumethatthesamespokedwheelwillalwaysbeusedonthefrontbutthereisachoiceofwheelsfortherear.

Task1.Provideatablegivingthewindspeedatwhichthepowerrequiredforasolidrearwheelislessthanforaspokedrearwheel.Thetableshouldincludethewindspeedsfordifferentroadgradesstartingfromzeropercenttotenpercentinonepercentincrements.(Roadgradeisdefinedtobetheratioofthetotalriseofahilldividedbythelengthoftheroad.Ifthehillisviewedasatriangle,thegradeisthesineoftheangleatthebottomofthehill.)Ariderstartsatthebottomofthehillataspeedof45kph,andthedecelerationoftheriderisproportionaltotheroadgrade.Ariderwillloseabout8kphforafivepercentgradeover100meters.

Task2.Provideanexampleofhowthetablecouldbeusedforaspecifictimetrialcourse.

Task3.Determineifthetableisanadequatemeansfordecidingonthewheelconfigurationandofferothersuggestionsastohowtomakethisdecision.

2001MCMB:EscapingaHurricane'sWrath(AnIllWind...)

EvacuatingthecoastofSouthCarolinaaheadofthepredictedlandfallofHurricaneFloydin1999ledtoamonumentaltrafficjam.TrafficslowedtoastandstillonInterstateI-26,whichistheprincipalroutegoinginlandfromCharlestontotherelativelysafehavenofColumbiainthecenterofthestate.Whatisnormallyaneasytwo-hourdrivetookupto18hourstocomplete.Manycarssimplyranoutofgasalongtheway.Fortunately,Floydturnednorthandsparedthestatethistime,butthepublicoutcryisforcingstateofficialstofindwaystoavoidarepeatofthistrafficnightmare.

TheprincipalproposalputforthtodealwiththisproblemisthereversaloftrafficonI-26,sothatbothsides,includingthecoastal-boundlanes,havetrafficheadedinlandfromCharlestontoColumbia.Planstocarrythisouthavebeenprepared(andpostedontheWeb)bytheSouthCarolinaEmergencyPreparednessDivision.TrafficreversalonprincipalroadsleadinginlandfromMyrtleBeachandHiltonHeadisalsoplanned.

AsimplifiedmapofSouthCarolinaisshown.Charlestonhasapproximately500,000people,MyrtleBeachhasabout200,000people,andanother250,000peoplearespreadoutalongtherestofthecoastalstrip.(Moreaccuratedata,ifsought,arewidelyavailable.)

Theinterstateshavetwolanesoftrafficineachdirectionexceptinthemetropolitanareaswheretheyhavethree.Columbia,anothermetroareaofaround500,000people,doesnothavesufficienthotelspacetoaccommodatetheevacuees(includingsomecomingfromfarthernorthbyotherroutes),sosometrafficcontinuesoutboundonI-26towardsSpartanburg;onI-77northtoCharlotte;andonI-20easttoAtlanta.In1999,trafficleavingColumbiagoingnorthwestwasmovingonlyveryslowly.Constructamodelfortheproblemtoinvestigatewhatstrategiesmayreducethecongestionobservedin1999.Herearethequestionsthatneedtobeaddressed:

Underwhatconditionsdoestheplanforturningthetwocoastal-boundlanesofI-26intotwolanesofColumbia-boundtraffic,essentiallyturningtheentireI-26intoone-waytraffic,significantlyimproveevacuationtrafficflow?

In1999,thesimultaneousevacuationofthestate'sentirecoastalregionwasordered.Wouldtheevacuationtrafficflowimproveunderanalternativestrategythatstaggerstheevacuation,perhapscounty-by-countyoversometimeperiodconsistentwiththepatternofhowhurricanesaffectthecoast?

SeveralsmallerhighwaysbesidesI-26extendinlandfromthecoast.Underwhatconditionswoulditimproveevacuationflowtoturnaroundtrafficonthese?

WhateffectwouldithaveonevacuationflowtoestablishmoretemporarysheltersinColumbia,toreducethetrafficleavingColumbia?

In1999,manyfamiliesleavingthecoastbroughtalongtheirboats,campers,andmotorhomes.Manydrovealloftheircars.Underwhatconditionsshouldthereberestrictionsonvehicletypesornumbersofvehiclesbroughtinordertoguaranteetimelyevacuation?

Ithasbeensuggestedthatin1999someofthecoastalresidentsofGeorgiaandFlorida,whowerefleeingtheearlierpredictedlandfallsofHurricaneFloydtothesouth,cameupI-95andcompoundedthetrafficproblems.Howbiganimpactcantheyhaveontheevacuationtrafficflow?Clearlyidentifywhatmeasuresofperformanceareusedtocomparestrategies.Required:Prepareashortnewspaperarticle,nottoexceedtwopages,explainingtheresultsandconclusionsofyourstudytothepublic.

Clearlyidentifywhatmeasuresofperformanceareusedtocomparestrategies.

Required:Prepareashortnewspaperarticle,nottoexceedtwopages,explainingtheresultsandconclusionsofyourstudytothepublic.

2002MCMA:WindandWaterspray

Anornamentalfountaininalargeopenplazasurroundedbybuildingssquirtswaterhighintotheair.Ongustydays,thewindblowssprayfromthefountainontopassersby.Thewater-flowfromthefountainiscontrolledbyamechanismlinkedtoananemometer(whichmeasureswindspeedanddirection)locatedontopofanadjacentbuilding.Theobjectiveofthiscontrolistoprovidepassersbywithanacceptablebalancebetweenanattractivespectacleandasoaking:Theharderthewindblows,thelowerthewatervolumeandheighttowhichthewaterissquirted,hencethelesssprayfallsoutsidethepoolarea.

Yourtaskistodeviseanalgorithmwhichusesdataprovidedbytheanemometertoadjustthewater-flowfromthefountainasthewindconditionschange.

2002MCMB:AirlineOverbooking

You'reallpackedandreadytogoonatriptovisityourbestfriendinNewYorkCity.Afteryoucheckinattheticketcounter,theairlineclerkannouncesthatyourflighthasbeenoverbooked.Passengersneedtocheckinimmediatelytodetermineiftheystillhaveaseat.

Historically,airlinesknowthatonlyacertainpercentageofpassengerswhohavemadereservationsonaparticularflightwillactuallytakethatflight.Consequently,mostairlinesoverbook-thatis,theytakemorereservationsthanthecapacityoftheaircraft.Occasionally,morepassengerswillwanttotakeaflightthanthecapacityoftheplaneleadingtooneormorepassengersbeingbumpedandthusunabletotaketheflightforwhichtheyhadreservations.

Airlinesdealwithbumpedpassengersinvariousways.Somearegivennothing,somearebookedonlaterflightsonotherairlines,andsomearegivensomekindofcashorairlineticketincentive.

Considertheoverbookingissueinlightofthecurrentsituation:LessflightsbyairlinesfrompointAtopointBHeightenedsecurityatandaroundairportsPassengers'fearLossofbillionsofdollarsinrevenuebyairlinestodate

Buildamathematicalmodelthatexaminestheeffectsthatdifferentoverbookingschemeshaveontherevenuereceivedbyanairlinecompanyinordertofindanoptimaloverbookingstrategy,i.e.,thenumberofpeoplebywhichanairlineshouldoverbookaparticularflightsothatthecompany'srevenueismaximized.Insurethatyourmodelreflectstheissuesabove,andconsideralternativesforhandling“bumped”passengers.Additionally,writeashortmemorandumtotheairline'sCEOsummarizingyourfindingsandanalysis.

2003MCMA:TheStuntPerson

Anexcitingactionsceneinamovieisgoingtobefilmed,andyouarethestuntcoordinator!Astuntpersononamotorcyclewilljumpoveranelephantandlandinapileofcardboardboxestocushiontheirfall.Youneedtoprotectthestuntperson,andalsouserelativelyfewcardboardboxes(lowercost,notseenbycamera,etc.).

Yourjobisto:

determinewhatsizeboxestouse

determinehowmanyboxestouse

determinehowtheboxeswillbestacked

determineifanymodificationstotheboxeswouldhelp

generalizetodifferentcombinedweights(stuntperson&motorcycle)anddifferentjumpheights

Notethat,in“TomorrowNeverDies”,theJamesBondcharacteronamotorcyclejumpsoverahelicopter.

2003MCMB:GammaKnifeTreatmentPlanning

Stereotacticradiosurgerydeliversasinglehighdoseofionizingradiationtoaradiographicallywell-defined,smallintracranial3Dbraintumorwithoutdeliveringanysignificantfractionoftheprescribeddosetothesurroundingbraintissue.Threemodalitiesarecommonlyusedinthisarea;theyarethegammaknifeunit,heavychargedparticlebeams,andexternalhigh-energyphotonbeamsfromlinearaccelerators.

Thegammaknifeunitdeliversasinglehighdoseofionizingradiationemanatingfrom201cobalt-60unitsourcesthroughaheavyhelmet.All201beamssimultaneouslyintersectattheisocenter,resultinginaspherical(approximately)dosedistributionattheeffectivedoselevels.Irradiatingtheisocentertodeliverdoseistermeda“shot.”Shotscanberepresentedasdifferentspheres.Fourinterchangeableoutercollimatorhelmetswithbeamchanneldiametersof4,8,14,and18mmareavailableforirradiatingdifferentsizevolumes.Foratargetvolumelargerthanoneshot,multipleshotscanbeusedtocovertheentiretarget.Inpractice,mosttargetvolumesaretreatedwith1to15shots.Thetargetvolumeisabounded,three-dimensionaldigitalimagethatusuallyconsistsofmillionsofpoints.

Thegoalofradiosurgeryistodepletetumorcellswhilepreservingnormalstructures.Sincetherearephysicallimitationsandbiologicaluncertaintiesinvolvedinthistherapyprocess,atreatmentplanneedstoaccountforallthoselimitationsanduncertainties.Ingeneral,anoptimaltreatmentplanisdesignedtomeetthefollowingrequirements.

Minimizethedosegradientacrossthetargetvolume.

Matchspecifiedisodosecontourstothetargetvolumes.

Matchspecifieddose-volumeconstraintsofthetargetandcriticalorgan.

Minimizetheintegraldosetotheentirevolumeofnormaltissuesororgans.

Constraindosetospecifiednormaltissuepointsbelowtolerancedoses.

Minimizethemaximumdosetocriticalvolumes.

Ingammaunittreatmentplanning,wehavethefollowingconstraints:

Prohibitshotsfromprotrudingoutsidethetarget.

Prohibitshotsfromoverlapping(toavoidhotspots).

Coverthetargetvolumewitheffectivedosageasmuchaspossible.Butatleast90%ofthetargetvolumemustbecoveredbyshots.

Useasfewshotsaspossible.

Yourtasksaretoformulatetheoptimaltreatmentplanningforagammaknifeunitasasphere-packingproblem,andproposeanalgorithmtofindasolution.Whiledesigningyouralgorithm,youmustkeepinmindthatyouralgorithmmustbereasonablyefficient.

2004MCMA:AreFingerprintsUnique?

Itisacommonplacebeliefthatthethumbprintofeveryhumanwhohaseverlivedisdifferent.Developandanalyzeamodelthatwillallowyoutoassesstheprobabilitythatthisistrue.Comparetheodds(thatyoufoundinthisproblem)ofmisidentificationbyfingerprintevidenceagainsttheoddsofmisidentificationbyDNAevidence.

2004MCMB:AFasterQuickPassSystem

“QuickPass”systemsareincreasinglyappearingtoreducepeople'stimewaitinginline,whetheritisattollbooths,amusementparks,orelsewhere.ConsiderthedesignofaQuickPasssystemforanamusementpark.TheamusementparkhasexperimentedbyofferingQuickPassesforseveralpopularridesasatest.Theideaisthatforcertainpopularridesyoucangotoakiosknearthatrideandinsertyourdailyparkentranceticket,andoutwillcomeaslipthatstatesthatyoucanreturntothatrideataspecifictimelater.Forexample,youinsertyourdailyparkentranceticketat1:15pm,andtheQuickPassstatesthatyoucancomebackbetween3:30and4:30pmwhenyoucanuseyoursliptoenterasecond,andpresumablymuchshorter,linethatwillgetyoutotheridefaster.TopreventpeoplefromobtainingQuickPassesforseveralridesatonce,theQuickPassmachinesallowyoutohaveonlyoneactiveQuickPassatatime.YouhavebeenhiredasoneofseveralcompetingconsultantstoimprovetheoperationofQuickPass.Customershavebeencomplainingaboutsomeanomaliesinthetestsystem.Forexample,customersobservedthatinoneinstanceQuickPasseswerebeingofferedforareturntimeaslongas4hourslater.Ashorttimelateronthesameride,theQuickPassesweregivenfortimesonlyanhourorsolater.Insomeinstances,thelinesforpeoplewithQuickpassesarenearlyaslongandslowastheregularlines.

TheproblemthenistoproposeandtestschemesforissuingQuickPassesinordertoincreasepeople'senjoymentoftheamusementpark.Partoftheproblemistodeterminewhatcriteriatouseinevaluatingalternativeschemes.Includeinyourreportanon-technicalsummaryforamusementparkexecutiveswhomustchoosebetweenalternativesfromcompetingconsultants.

2005MCMA:FloodPlanning

LakeMurrayincentralSouthCarolinaisformedbyalargeearthendam,whichwascompletedin1930forpowerproduction.Modelthefloodingdownstreamintheeventthereisacatastrophicearthquakethatbreachesthedam.

Twoparticularquestions:

RawlsCreekisayear-roundstreamthatflowsintotheSaludaRiverashortdistancedownriverfromthedam.HowmuchfloodingwilloccurinRawlsCreekfromadamfailure,andhowfarbackwillitextend?

CouldthefloodbesomassivedownstreamthatwaterwouldreachuptotheS.C.StateCapitolBuilding,whichisonahilloverlookingtheCongareeRiver?

2005MCMB:Tollbooths

Heavily-traveledtollroadssuchastheGardenStateParkway,Interstate95,andsoforth,aremulti-lanedividedhighwaysthatareinterruptedatintervalsbytollplazas.Becausecollectingtollsisusuallyunpopular,itisdesirabletominimizemotoristannoyancebylimitingtheamountoftrafficdisruptioncausedbythetollplazas.Commonly,amuchlargernumberoftollboothsisprovidedthanthenumberoftravellanesenteringthetollplaza.Uponenteringthetollplaza,theflowofvehiclesfansouttothelargernumberoftollbooths,andwhenleavingthetollplaza,theflowofvehiclesisrequiredtosqueezebackdowntoanumberoftravellanesequaltothenumberoftravellanesbeforethetollplaza.Consequently,whentrafficisheavy,congestionincreasesupondeparturefromthetollplaza.Whentrafficisveryheavy,congestionalsobuildsattheentrytothetollplazabecauseofthetimerequiredforeachvehicletopaythetoll.

Makeamodeltohelpyoudeterminetheoptimalnumberoftollboothstodeployinabarrier-tollplaza.Explicitlyconsiderthescenariowherethereisexactlyonetollboothperincomingtravellane.Underwhatconditionsisthismoreorlesseffectivethanthecurrentpractice?Notethatthedefinitionof“optimal”isuptoyoutodetermine.

2006MCMA:PositioningandMovingSprinklerSystemsforIrrigation

Thereareawidevarietyoftechniquesavailableforirrigatingafield.Thetechnologiesrangefromadvanceddripsystemstoperiodicflooding.Oneofthesystemsthatisusedonsmallerranchesistheuseof“handmove”irrigationsystems.Lightweightaluminumpipeswithsprinklerheadsareputinplaceacrossfields,andtheyaremovedbyhandatperiodicintervalstoinsurethatthewholefieldreceivesanadequateamountofwater.Thistypeofirrigationsystemischeaperandeasiertomaintainthanothersystems.Itisalsoflexible,allowingforuseonawidevarietyoffieldsandcrops.Thedisadvantageisthatitrequiresagreatdealoftimeandefforttomoveandsetuptheequipmentatregularintervals.

Giventhatthistypeofirrigationsystemistobeused,howcanitbeconfiguredtominimizetheamountoftimerequiredtoirrigateafieldthatis80metersby30meters?Forthistaskyouareaskedtofindanalgorithmtodeterminehowtoirrigatetherectangularfieldthatminimizestheamountoftimerequiredbyaranchertomaintaintheirrigationsystem.Onepipesetisusedinthefield.Youshoulddeterminethenumberofsprinklersandthespacingbetweensprinklers,andyoushouldfindascheduletomovethepipes,includingwheretomovethem.

Apipesetconsistsofanumberofpipesthatcanbeconnectedtogetherinastraightline.Eachpipehasa10cminnerdiameterwithrotatingspraynozzlesthathavea0.6cminnerdiameter.Whenputtogethertheresultingpipeis20meterslong.Atthewatersource,thepressureis420Kilo-Pascal’sandhasaflowrateof150litersperminute.Nopartofthefieldshouldreceivemorethan0.75cmperhourofwater,andeachpartofthefieldshouldreceiveatleast2centimetersofwaterevery4days.Thetotalamountofwatershouldbeappliedasuniformlyaspossible.

2006MCMB:WheelChairAccessatAirports

Oneofthefrustrationswithairtravelistheneedtoflythroughmultipleairports,andeachstopgenerallyrequireseachtravelertochangetoadifferentairplane.Thiscanbeespeciallydifficultforpeoplewhoarenotabletoeasilywalktoadifferentflight'swaitingarea.Oneofthewaysthatanairlinecanmakethetransitioneasieristoprovideawheelchairandanescorttothosepeoplewhoaskforhelp.Itisgenerallyknownwellinadvancewhichpassengersrequirehelp,butitisnotuncommontoreceivenoticewhenapassengerfirstregistersattheairport.Inrareinstancesanairlinemaynotreceivenoticefromapassengeruntiljustpriortolanding.

Airlinesareunderconstantpressuretokeeptheircostsdown.Wheelchairswearoutandareexpensiveandrequiremaintenance.Thereisalsoacostformakingtheescortsavailable.Moreover,wheelchairsandtheirescortsmustbeconstantlymovedaroundtheairportsothattheyareavailabletopeoplewhentheirflightlands.Insomelargeairportsthetimerequiredtomoveacrosstheairportisnontrivial.Thewheelchairsmustbestoredsomewhere,butspaceisexpensiveandseverelylimitedinanairportterminal.Also,wheelchairsleftinhightrafficareasrepresentaliabilityriskaspeopletrytomovearoundthem.Finally,oneofthebiggestcostsisthecostofholdingaplaneifsomeonemustwaitforanescortandbecomeslatefortheirflight.Thelattercostisespeciallytroublingbecauseitcanaffecttheairline'saverageflightdelaywhichcanleadtofewerticketsalesaspotentialcustomersmaychoosetoavoidanairline.

EpsilonAirlineshasdecidedtoaskathirdpartytohelpthemobtainadetailedanalysisoftheissuesandcostsofkeepingandmaintainingwheelchairsandescortsavailableforpassengers.Theairlineneedstofindawaytoschedulethemovementofwheelchairsthroughouteachdayinacosteffectiveway.Theyalsoneedtofindanddefinethecostsforbudgetplanninginboththeshortandlongterm.

EpsilonAirlineshasaskedyourconsultantgrouptoputtogetherabidtohelpthemsolvetheirproblem.Yourbidshouldincludeanoverviewandanalysisofthesituationtohelpthemdecideifyoufullyunderstandtheirproblem.Theyrequireadetaileddescriptionofanalgorithmthatyouwouldliketoimplementwhichcandeterminewheretheescortsandwheelchairsshouldbeandhowtheyshouldmovethroughouteachday.Thegoalistokeepthetotalcostsaslowaspossible.Yourbidisoneofmanythattheairlinewillconsider.Youmustmakeastrongcaseastowhyyoursolutionisthebestandshowthatitwillbeabletohandleawiderangeofairportsunderavarietyofcircumstances.

Yourbidshouldalsoincludeexamplesofhowthealgorithmwouldworkforalarge(atleast4concourses),amedium(atleasttwoconcourses),andasmallairport(oneconcourse)underhighandlowtrafficloads.Youshoulddetermineallpotentialcostsandbalancetheirrespectiveweights.Finally,aspopulationsbegintoincludeahigherpercentageofolderpeoplewhohavemoretimetotravelbutmayrequiremoreaid,yourreportshouldincludeprojectionsofpotentialcostsandneedsinthefuturewithrecommendationstomeetfutureneeds.

2007MCMA:Gerrymandering

GerrymanderingTheUnitedStatesConstitutionprovidesthattheHouseofRepresentativesshallbecomposedofsomenumber(currently435)ofindividualswhoareelectedfromeachstateinproportiontothestate’spopulationrelativetothatofthecountryasawhole.Whilethisprovidesawayofdetermininghowmanyrepresentativeseachstatewillhave,itsaysnothingabouthowthedistrictrepresentedbyaparticularrepresentativeshallbedeterminedgeographically.Thisoversighthasledtoegregious(atleastsomepeoplethinkso,usuallynottheincumbent)districtshapesthatlook“unnatural”bysomestandards.

Hencethefollowingquestion:Supposeyouweregiventheopportunitytodrawcongressionaldistrictsforastate.Howwouldyoudosoasapurely“baseline”exercisetocreatethe“simplest”shapesforallthedistrictsinastate?Therulesincludeonlythateachdistrictinthestatemustcontainthesamepopulation.Thedefinitionof“simple”isuptoyou;butyouneedtomakeaconvincingargumenttovotersinthestatethatyoursolutionisfair.Asanapplicationofyourmethod,drawgeographicallysimplecongressionaldistrictsforthestateofNewYork.

2007MCMB:TheAirplaneSeatingProblem

Airlinesarefreetoseatpassengerswaitingtoboardanaircraftinanyorderwhatsoever.Ithasbecomecustomarytoseatpassengerswithspecialneedsfirst,followedbyfirst-classpassengers(whositatthefrontoftheplane).Thencoachandbusiness-classpassengersareseatedbygroupsofrows,beginningwiththerowatthebackoftheplaneandproceedingforward.

Apartfromconsiderationofthepassengers’waittime,fromtheairline’spointofview,timeismoney,andboardingtimeisbestminimized.Theplanemakesmoneyfortheairlineonlywhenitisinmotion,andlongboardingtimeslimitthenumberoftripsthataplanecanmakeinaday.

Thedevelopmentoflargerplanes,suchastheAirbusA380(800passengers),accentuatetheproblemofminimizingboarding(anddeboarding)time.

Deviseandcompareproceduresforboardinganddeboardingplaneswithvaryingnumbersofpassengers:small(85–210),midsize(210–330),andlarge(450–800).

Prepareanexecutivesummary,nottoexceedtwosingle-spacedpages,inwhichyousetoutyourconclusionstoanaudienceofairlineexecutives,gateagents,andflightcrews.

AnarticleappearedintheNYTimesNov14,2006addressingprocedurescurrentlybeingfollowedandtheimportancetotheairlineoffindingbettersolutions.Thearticlecanbeseenat:

\o"/2006/11/14/business/14boarding.html"

/2006/11/14/business/14boarding.html

2008MCMA:TakeaBath

Considertheeffectsonlandfromthemeltingofthenorthpolaricecapduetothepredictedincreaseinglobaltemperatures.Specifically,modeltheeffectsonthecoastofFloridaeverytenyearsforthenext50yearsduetothemelting,withparticularattentiongiventolargemetropolitanareas.Proposeappropriateresponsestodealwiththis.Acarefuldiscussionofthedatausedisanimportantpartoftheanswer.

2008MCMB:CreatingSudokuPuzzles

DevelopanalgorithmtoconstructSudokupuzzlesofvaryingdifficulty.Developmetricstodefineadifficultylevel.Thealgorithmandmetricsshouldbeextensibletoavaryingnumberofdifficultylevels.Youshouldillustratethealgorithmwithatleast4difficultylevels.Youralgorithmshouldguaranteeauniquesolution.Analyzethecomplexityofyouralgorithm.Yourobjectiveshouldbetominimizethecomplexityofthealgorithmandmeettheaboverequirements.

2009MCMA:DesigningaTrafficCircle

Manycitiesandcommunitieshavetrafficcircles—fromlargeoneswithmanylanesinthecircle(suchasattheArcdeTriompheinParisandtheVictoryMonumentinBangkok)tosmalloneswithoneortwolanesinthecircle.Someofthesetrafficcirclespositionastopsignorayieldsignoneveryincomingroadthatgivesprioritytotrafficalreadyinthecircle;somepositionayieldsigninthecircleateachincomingroadtogiveprioritytoincomingtraffic;andsomepositionatrafficlightoneachincomingroad(withnorightturnallowedonaredlight).Otherdesignsmayalsobepossible.

Thegoalofthisproblemistouseamodeltodeterminehowbesttocontroltrafficflowin,around,andoutofacircle.Stateclearlytheobjective(s)youuseinyourmodelformakingtheoptimalchoiceaswellasthefactorsthataffectthischoice.IncludeaTechnicalSummaryofnotmorethantwodouble-spacedpagesthatexplainstoaTrafficEngineerhowtouseyourmodeltohelpchoosetheappropriateflow-controlmethodforanyspecifictrafficcircle.Thatis,summarizetheconditionsunderwhicheachtypeoftraffic-controlmethodshouldbeused.Whentra