历年MCM题目

2002 MCM Problems

Problem A

Authors: Tjalling Ypma Title: Wind and Waterspray

An ornamental fountain in a large open plaza surrounded by buildings squirts water high into the air. On gusty days, the wind blows spray from the fountain onto passersby. The water-flow from the fountain is controlled by a mechanism linked to an anemometer (which measures wind speed and

direction) located on top of an adjacent building. The objective of this control is to provide passersby with an acceptable balance between an attractive spectacle and a soaking: The harder the wind blows, the lower the water volume and height to which the water is squirted, hence the less spray falls outside the pool area.

Your task is to devise an algorithm which uses data provided by the

anemometer to adjust the water-flow from the fountain as the wind conditions change.

Problem B

Authors: Bill Fox and Rich West Title: Airline Overbooking

You're all packed and ready to go on a trip to visit your best friend in New York City. After you check in at the ticket counter, the airline clerk announces that your flight has been overbooked. Passengers need to check in immediately to determine if they still have a seat.

Historically, airlines know that only a certain percentage of passengers who have made reservations on a particular flight will actually take that flight. Consequently, most airlines overbook-that is, they take more reservations than the capacity of the aircraft. Occasionally, more passengers will want to take a flight than the capacity of the plane leading to one or more passengers

being bumped and thus unable to take the flight for which they had reservations.

Airlines deal with bumped passengers in various ways. Some are given

nothing, some are booked on later flights on other airlines, and some are given some kind of cash or airline ticket incentive.

Consider the overbooking issue in light of the current situation: Less flights by airlines from point A to point B Heightened security at and around airports Passengers' fear

Loss of billions of dollars in revenue by airlines to date

Build a mathematical model that examines the effects that different

overbooking schemes have on the revenue received by an airline company in order to find an optimal overbooking strategy, i.e., the number of people by which an airline should overbook a particular flight so that the company's revenue is maximized. Insure that your model reflects the issues above, and consider alternatives for handling \short memorandum to the airline's CEO summarizing your findings and analysis.

2003 MCM Problems

PROBLEM A: The Stunt Person

An exciting action scene in a movie is going to be filmed, and you are the stunt coordinator! A stunt person on a motorcycle will jump over an elephant and land in a pile of cardboard boxes to cushion their fall. You need to protect the stunt person, and also use relatively few cardboard boxes (lower cost, not seen by camera, etc.). Your job is to:

? ? ? ? ?

determine what size boxes to use determine how many boxes to use

determine how the boxes will be stacked

determine if any modifications to the boxes would help

generalize to different combined weights (stunt person & motorcycle) and different jump heights

Note that, in \Never Dies\the James Bond character on a motorcycle jumps over a helicopter.

PROBLEM B: Gamma Knife Treatment Planning

Stereotactic radiosurgery delivers a single high dose of ionizing radiation to a radiographically well-defined, small intracranial 3D brain tumor without delivering any significant fraction of the prescribed dose to the surrounding brain tissue. Three modalities are commonly used in this area; they are the gamma knife unit, heavy charged particle beams, and external high-energy photon beams from linear accelerators.

The gamma knife unit delivers a single high dose of ionizing radiation emanating from 201 cobalt-60 unit sources through a heavy helmet. All 201 beams simultaneously intersect at the isocenter, resulting in a spherical (approximately) dose distribution at the effective dose levels. Irradiating the isocenter to deliver dose is termed a ―shot.‖ Shots can be represented as different spheres. Four interchangeable outer collimator helmets with beam channel diameters of 4, 8, 14, and 18 mm are available for irradiating different size volumes. For a target volume larger than one shot, multiple shots can be used to cover the entire target. In practice, most target volumes are treated with 1 to 15 shots. The target volume is a bounded, three-dimensional digital image that usually consists of millions of points.

The goal of radiosurgery is to deplete tumor cells while preserving normal structures. Since there are physical limitations and biological uncertainties involved in this therapy process, a treatment plan needs to account for all those limitations and uncertainties. In general, an optimal treatment plan is designed to meet the following requirements.

1. Minimize the dose gradient across the target volume. 2. Match specified isodose contours to the target volumes.

3. Match specified dose-volume constraints of the target and critical

organ.

4. Minimize the integral dose to the entire volume of normal tissues or

organs.

5. Constrain dose to specified normal tissue points below tolerance doses. 6. Minimize the maximum dose to critical volumes.

In gamma unit treatment planning, we have the following constraints:

1. Prohibit shots from protruding outside the target. 2. Prohibit shots from overlapping (to avoid hot spots).

3. Cover the target volume with effective dosage as much as possible. But

at least 90% of the target volume must be covered by shots. 4. Use as few shots as possible.

Your tasks are to formulate the optimal treatment planning for a gamma knife unit as a sphere-packing problem, and propose an algorithm to find a solution. While designing your algorithm, you must keep in mind that your algorithm must be reasonably efficient.

2004 MCM A: Are Fingerprints Unique?

It is a commonplace belief that the thumbprint of every human who has ever lived is different. Develop and analyze a model that will allow you to assess the probability that this is true. Compare the odds (that you found in this problem) of misidentification by fingerprint evidence against the odds of misidentification by DNA evidence.

2004 MCM B: A Faster QuickPass System

―QuickPass‖ systems are increasingly appearing to reduce people's time waiting in line, whether it is at tollbooths, amusement parks, or elsewhere. Consider the design of a QuickPass system for an amusement park. The amusement park has experimented by offering QuickPasses for several

popular rides as a test. The idea is that for certain popular rides you can go to a kiosk near that ride and insert your daily park entrance ticket, and out will come a slip that states that you can return to that ride at a specific time later. For example, you insert your daily park entrance ticket at 1:15 pm, and the QuickPass states that you can come back between 3:30 and 4:30 pm when you can use your slip to enter a second, and presumably much shorter, line that will get you to the ride faster. To prevent people from obtaining QuickPasses for several rides at once, the QuickPass machines allow you to have only one active QuickPass at a time. You have been hired as one of several competing consultants to improve the operation of QuickPass. Customers have been complaining about some anomalies in the test system. For example,

customers observed that in one instance QuickPasses were being offered for a return time as long as 4 hours later. A short time later on the same ride, the QuickPasses were given for times only an hour or so later. In some instances,

the lines for people with Quickpasses are nearly as long and slow as the regular lines.

The problem then is to propose and test schemes for issuing QuickPasses in order to increase people's enjoyment of the amusement park. Part of the

problem is to determine what criteria to use in evaluating alternative schemes. Include in your report a non-technical summary for amusement park executives who must choose between alternatives from competing consultants.

2005 MCM A: Flood Planning

Lake Murray in central South Carolina is formed by a large earthen dam, which was completed in 1930 for power production. Model the flooding

downstream in the event there is a catastrophic earthquake that breaches the dam.

Two particular questions:

Rawls Creek is a year-round stream that flows into the Saluda River a short distance downriver from the dam. How much flooding will occur in Rawls Creek from a dam failure, and how far back will it extend?

Could the flood be so massive downstream that water would reach up to the S.C. State Capitol Building, which is on a hill overlooking the Congaree River?

2005 MCM B: Tollbooths

Heavily-traveled toll roads such as the Garden State Parkway, Interstate 95, and so forth, are multi-lane divided highways that are interrupted at intervals by toll plazas. Because collecting tolls is usually unpopular, it is desirable to minimize motorist annoyance by limiting the amount of traffic disruption caused by the toll plazas. Commonly, a much larger number of tollbooths is provided than the number of travel lanes entering the toll plaza. Upon

entering the toll plaza, the flow of vehicles fans out to the larger number of tollbooths, and when leaving the toll plaza, the flow of vehicles is required to squeeze back down to a number of travel lanes equal to the number of travel lanes before the toll plaza. Consequently, when traffic is heavy, congestion increases upon departure from the toll plaza. When traffic is very heavy, congestion also builds at the entry to the toll plaza because of the time required for each vehicle to pay the toll.

Make a model to help you determine the optimal number of tollbooths to deploy in a barrier-toll plaza. Explicitly consider the scenario where there is exactly one tollbooth per incoming travel lane. Under what conditions is this more or less effective than the current practice? Note that the definition of ―optimal‖ is up to you to determine.

2006 MCM A: Positioning and Moving Sprinkler Systems for Irrigation

There are a wide variety of techniques available for irrigating a field. The technologies range from advanced drip systems to periodic flooding. One of the systems that is used on smaller ranches is the use of ―hand move‖

irrigation systems. Lightweight aluminum pipes with sprinkler heads are put in place across fields, and they are moved by hand at periodic intervals to insure that the whole field receives an adequate amount of water. This type of irrigation system is cheaper and easier to maintain than other systems. It is also flexible, allowing for use on a wide variety of fields and crops. The

disadvantage is that it requires a great deal of time and effort to move and set up the equipment at regular intervals.

Given that this type of irrigation system is to be used, how can it be configured to minimize the amount of time required to irrigate a field that is 80 meters by 30 meters? For this task you are asked to find an algorithm to determine how to irrigate the rectangular field that minimizes the amount of time required by a rancher to maintain the irrigation system. One pipe set is used in the field. You should determine the number of sprinklers and the spacing between

sprinklers, and you should find a schedule to move the pipes, including where to move them.

A pipe set consists of a number of pipes that can be connected together in a straight line. Each pipe has a 10 cm inner diameter with rotating spray nozzles that have a 0.6 cm inner diameter. When put together the resulting pipe is 20 meters long. At the water source, the pressure is 420 Kilo- Pascal’s and has a flow rate of 150 liters per minute. No part of the field should receive more than 0.75 cm per hour of water, and each part of the field should receive at least 2 centimeters of water every 4 days. The total amount of water should be applied as uniformly as possible.

2006 MCM B: Wheel Chair Access at Airports

One of the frustrations with air travel is the need to fly through multiple

airports, and each stop generally requires each traveler to change to a different

airplane. This can be especially difficult for people who are not able to easily walk to a different flight's waiting area. One of the ways that an airline can make the transition easier is to provide a wheel chair and an escort to those people who ask for help. It is generally known well in advance which

passengers require help, but it is not uncommon to receive notice when a passenger first registers at the airport. In rare instances an airline may not receive notice from a passenger until just prior to landing.

Airlines are under constant pressure to keep their costs down. Wheel chairs wear out and are expensive and require maintenance. There is also a cost for making the escorts available. Moreover, wheel chairs and their escorts must be constantly moved around the airport so that they are available to people when their flight lands. In some large airports the time required to move across the airport is nontrivial. The wheel chairs must be stored somewhere, but space is expensive and severely limited in an airport terminal. Also, wheel chairs left in high traffic areas represent a liability risk as people try to move around them. Finally, one of the biggest costs is the cost of holding a plane if someone must wait for an escort and becomes late for their flight. The latter cost is especially troubling because it can affect the airline's average flight delay which can lead to fewer ticket sales as potential customers may choose to avoid an airline.

Epsilon Airlines has decided to ask a third party to help them obtain a detailed analysis of the issues and costs of keeping and maintaining wheel chairs and escorts available for passengers. The airline needs to find a way to schedule the movement of wheel chairs throughout each day in a cost effective way. They also need to find and define the costs for budget planning in both the short and long term.

Epsilon Airlines has asked your consultant group to put together a bid to help them solve their problem. Your bid should include an overview and analysis of the situation to help them decide if you fully understand their problem. They require a detailed description of an algorithm that you would like to

implement which can determine where the escorts and wheel chairs should be and how they should move throughout each day. The goal is to keep the total costs as low as possible. Your bid is one of many that the airline will consider. You must make a strong case as to why your solution is the best and show that it will be able to handle a wide range of airports under a variety of circumstances.

Your bid should also include examples of how the algorithm would work for a large (at least 4 concourses), a medium (at least two concourses), and a small airport (one concourse) under high and low traffic loads. You should

determine all potential costs and balance their respective weights. Finally, as populations begin to include a higher percentage of older people who have

more time to travel but may require more aid, your report should include projections of potential costs and needs in the future with recommendations to meet future needs.

2007 MCM A: Gerrymandering

Gerrymandering The United States Constitution provides that the House of Representatives shall be composed of some number (currently 435) of individuals who are elected from each state in proportion to the state’s

population relative to that of the country as a whole. While this provides a way of determining how many representatives each state will have, it says nothing about how the district represented by a particular representative shall be determined geographically. This oversight has led to egregious (at least some people think so, usually not the incumbent) district shapes that look ―unnatural‖ by some standards.

Hence the following question: Suppose you were given the opportunity to draw congressional districts for a state. How would you do so as a purely

―baseline‖ exercise to create the ―simplest‖ shapes for all the districts in a state? The rules include only that each district in the state must contain the same population. The definition of ―simple‖ is up to you; but you need to make a convincing argument to voters in the state that your solution is fair. As an application of your method, draw geographically simple congressional districts for the state of New York.

2007 MCM B: The Airplane Seating Problem

Airlines are free to seat passengers waiting to board an aircraft in any order whatsoever. It has become customary to seat passengers with special needs first, followed by first-class passengers (who sit at the front of the plane). Then coach and business-class passengers are seated by groups of rows, beginning with the row at the back of the plane and proceeding forward.

Apart from consideration of the passengers’ wait time, from the airline’s point of view, time is money, and boarding time is best minimized. The plane makes money for the airline only when it is in motion, and long boarding times limit the number of trips that a plane can make in a day.

The development of larger planes, such as the Airbus A380 (800 passengers), accentuate the problem of minimizing boarding (and deboarding) time.

Devise and compare procedures for boarding and deboarding planes with

varying numbers of passengers: small (85–210), midsize (210–330), and large (450–800).

Prepare an executive summary, not to exceed two single-spaced pages, in which you set out your conclusions to an audience of airline executives, gate agents, and flight crews.

An article appeared in the NY Times Nov 14, 2006 addressing procedures currently being followed and the importance to the airline of finding better solutions. The article can be seen at:

http://travel2.nytimes.com/2006/11/14/business/14boarding.html

2008 MCM A: Take a Bath

Consider the effects on land from the melting of the north polar ice cap due to the predicted increase in global temperatures. Specifically, model the effects on the coast of Florida every ten years for the next 50 years due to the melting, with particular attention given to large metropolitan areas. Propose

appropriate responses to deal with this. A careful discussion of the data used is an important part of the answer.

2008 MCM B: Creating Sudoku Puzzles

Develop an algorithm to construct Sudoku puzzles of varying difficulty.

Develop metrics to define a difficulty level. The algorithm and metrics should be extensible to a varying number of difficulty levels. You should illustrate the algorithm with at least 4 difficulty levels. Your algorithm should guarantee a unique solution. Analyze the complexity of your algorithm. Your objective should be to minimize the complexity of the algorithm and meet the above requirements.

2009 MCM A: Designing a Traffic Circle

Many cities and communities have traffic circles—from large ones with many lanes in the circle (such as at the Arc de Triomphe in Paris and the Victory Monument in Bangkok) to small ones with one or two lanes in the circle. Some of these traffic circles position a stop sign or a yield sign on every incoming road that gives priority to traffic already in the circle; some position a yield sign in the circle at each incoming road to give priority to incoming traffic; and some position a traffic light on each incoming road (with no right turn allowed on a red light). Other designs may also be possible.

The goal of this problem is to use a model to determine how best to control traffic flow in, around, and out of a circle. State clearly the objective(s) you use in your model for making the optimal choice as well as the factors that affect this choice. Include a Technical Summary of not more than two double-spaced pages that explains to a Traffic Engineer how to use your model to help choose the appropriate flow-control method for any specific traffic circle. That is, summarize the conditions under which each type of traffic-control method should be used. When traffic lights are recommended, explain a method for determining how many seconds each light should remain green (which may vary according to the time of day and other factors). Illustrate how your model works with specific examples.

2009 MCM B: Energy and the Cell Phone

This question involves the ―energy‖ consequences of the cell phone revolution. Cell phone usage is mushrooming, and many people are using cell phones and giving up their landline telephones. What is the consequence of this in terms of electricity use? Every cell phone comes with a battery and a recharger. Requirement 1

Consider the current US, a country of about 300 million people. Estimate from available data the number H of households, with m members each, that in the past were serviced by landlines. Now, suppose that all the landlines are replaced by cell phones; that is, each of the m members of the household has a cell phone. Model the consequences of this change for electricity utilization in the current US, both during the transition and during the steady state. The analysis should take into account the need for charging the batteries of the cell phones, as well as the fact that cell phones do not last as long as landline phones (for example, the cell phones get lost and break). Requirement 2

Consider a second ―Pseudo US‖—a country of about 300 million people with about the same economic status as the current US. However, this emerging country has neither landlines nor cell phones. What is the optimal way of

providing phone service to this country from an energy perspective? Of course, cell phones have many social consequences and uses that landline phones do not allow. A discussion of the broad and hidden consequences of having only landlines, only cell phones, or a mixture of the two is welcomed. Requirement 3

Cell phones periodically need to be recharged. However, many people always keep their recharger plugged in. Additionally, many people charge their phones every night, whether they need to be recharged or not. Model the

energy costs of this wasteful practice for a Pseudo US based upon your answer to Requirement 2. Assume that the Pseudo US supplies electricity from oil. Interpret your results in terms of barrels of oil. Requirement 4

Estimates vary on the amount of energy that is used by various recharger types (TV, DVR, computer peripherals, and so forth) when left plugged in but not charging the device. Use accurate data to model the energy wasted by the current US in terms of barrels of oil per day. Requirement 5

Now consider population and economic growth over the next 50 years. How might a typical Pseudo US grow? For each 10 years for the next 50 years,

predict the energy needs for providing phone service based upon your analysis in the first three requirements. Again, assume electricity is provided from oil. Interpret your predictions in term of barrels of oil.

2010MCM

PROBLEM A: The Sweet Spot

Explain the ―sweet spot‖ on a baseball bat.

Every hitter knows that there is a spot on the fat part of a baseball bat where maximum power

is transferred to the ball when hit. Why isn’t this spot at the end of the bat? A simple

explanation based on torque might seem to identify the end of the bat as the sweet spot, but

this is known to be empirically incorrect. Develop a model that helps explain this empirical finding.

Some players believe that ―corking‖ a bat (hollowing out a cylinder in the head of the bat and

filling it with cork or rubber, then replacing a wood cap) enhances the ―sweet spot‖ effect.

Augment your model to confirm or deny this effect. Does this explain why Major League

Baseball prohibits ―corking‖?

Does the material out of which the bat is constructed matter? That is, does this model predict

different behavior for wood (usually ash) or metal (usually aluminum) bats? Is this why Major

League Baseball prohibits metal bats?

PROBLEM B: Criminology

In 1981 Peter Sutcliffe was convicted of thirteen murders and subjecting a number of other people to vicious attacks. One of the methods used to narrow the search for Mr. Sutcliffe was to find a ―center of mass‖ of the locations of the attacks. In the end, the suspect happened to live in the same town

predicted by this technique. Since that time, a number of more sophisticated techniques have been developed to determine the ―geographical profile‖ of a suspected serial criminal based on the locations of the crimes.

Your team has been asked by a local police agency to develop a method to aid in their investigations of serial criminals. The approach that you develop should make use of at least two different schemes to generate a geographical profile. You should develop a technique to combine the results of the different schemes and generate a useful prediction for law enforcement officers. The prediction should provide some kind of estimate or guidance about possible locations of the next crime based on the time and locations of the past crime scenes. If you make use of any other evidence in your estimate, you must

provide specific details about how you incorporate the extra information. Your method should also provide some kind of estimate about how reliable the estimate will be in a given situation, including appropriate warnings.

In addition to the required one-page summary, your report should include an additional two-page executive summary. The executive summary should

provide a broad overview of the potential issues. It should provide an overview of your approach and describe situations when it is an appropriate tool and situations in which it is not an appropriate tool. The executive summary will be read by a chief of police and should include technical details appropriate to the intended audience.

2011MCM

PROBLEM A: Snowboard Course

Determine the shape of a snowboard course (currently known as a ―halfpipe‖) to maximize the production of ―vertical air‖ by a skilled snowboarder.

\

Tailor the shape to optimize other possible requirements, such as maximum twist in the air.

What tradeoffs may be required to develop a ―practical‖ course?

PROBLEM B: Repeater Coordination

The VHF radio spectrum involves line-of-sight transmission and reception. This limitation can be overcome by ―repeaters,‖ which pick up weak signals, amplify them, and retransmit them on a different frequency. Thus, using a repeater, low-power users (such as mobile stations) can communicate with one another in situations where direct user-to-user contact would not be possible. However, repeaters can interfere with one another unless they are far enough apart or transmit on sufficiently separated frequencies.

In addition to geographical separation, the ―continuous tone-coded squelch system‖ (CTCSS), sometimes nicknamed ―private line‖ (PL), technology can be used to mitigate interference problems. This system associates to each

repeater a separate subaudible tone that is transmitted by all users who wish to communicate through that repeater. The repeater responds only to received signals with its specific PL tone. With this system, two nearby repeaters can share the same frequency pair (for receive and transmit); so more repeaters (and hence more users) can be accommodated in a particular area.

For a circular flat area of radius 40 miles radius, determine the minimum number of repeaters necessary to accommodate 1,000 simultaneous users. Assume that the spectrum available is 145 to 148 MHz, the transmitter

frequency in a repeater is either 600 kHz above or 600 kHz below the receiver frequency, and there are 54 different PL tones available.

How does your solution change if there are 10,000 users?

Discuss the case where there might be defects in line-of-sight propagation caused by mountainous areas.

本文来源：https://www.bwwdw.com/article/gd8a.html