美国数学建模比赛历年试题.doc

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 "Tomorrow 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.

2002 Contest 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 "bumped" passengers. Additionally, write a short memorandum to the airline's CEO summarizing your findings and analysis.

MCM2000
Problem A Air traffic Control
To improve safety and reduce air traffic controller workload, the Federal Aviation Agency (FAA) is considering adding software to the air traffic control system that would automatically detect potential aircraft flight path conflicts and alert the controller. To that end, an analyst at the FAA 　r traffic control system that would automatically detect potential aircraft flight path conflicts and alert the controller. To that end, an analyst at the FAA has posed the following problems
Requirement A: Given two airplanes flying in space, when should the air traffic controller 　ld the air traffic controller consider the objects to be too close and to require intervention?
Requirement B: An airspace sector is the section of three-dimensional airspace that one air traffic controller controls. Given any airspace sector, how we measure how complex it is from an air traffic workload perspective? To what extent is complexity determined by the number of we measure how complex it is from an air traffic workload perspective? To what extent is complexity determined by the number of aircraft simultaneously passing through that sector (1) at any one instant? (2) During any given interval of time? (3) During particular time of day? How does the number of potential conflicts arising during those periods affect complexity?
Does the presence of additional software tools to automatically predict conflicts and alert the controller reduce or add to this complexity?
In addition to the guidelines for your report, write a summary (no more than two pages) that the FAA analyst can present to Jane Garvey, the FAA Administrator, to defend your conclusions
Problem B Radio Channel Assignments
We seek to model the assignment of radio channels to a symmetric network of transmitter locations over a large planar area, so as to avoid interference. One basic approach is to partition the region into regular hexagons in a grid (honeycomb-style), as shown in Figure 1, where a transmitter is located at the center of each hexagon.
An interval of the frequency spectrum is to be allotted for transmitter frequencies. The interval will be divided into regularly spaced channels, which we represent by integers 1, 2, 3, ... . Each transmitter will be assigned one positive integer channel. The same channel can be used at many locations, provided that interference from nearby transmitters is avoided. Our goal is to minimize the width of the interval in the frequency spectrum that is needed to assign channels subject to some constraints. This is achieved with the concept of a span. The span is the minimum, over all assignments satisfying the constraints, of the largest channel used at any location. It is not required that every channel smaller than the span be used in an assignment that attains the span.
Let s be the length of a side of one of the hexagons. We concentrate on the case that there are two levels of interference
Requirement A: There are several constraints on frequency assignments. First, no two transmitters within distance of each other can be given the same channel. Second, due to spectral spreading, transmitters within distance 2s of each other must not be given the same or adjacent channels: Their channels must differ by at least 2. Under these constraints, what can we say about the span in,
Requirement B: Repeat Requirement A, assuming the grid in the example spreads arbitrarily far in all directions.
Requirement C: Repeat Requirements A and B, except assume now more generally that channels for transmitters within distance differ by at least some given integer k, while those at distance at most must still differ by at least one. What can we say about the span and about efficient strategies for designing assignments, as a function of k?
Requirement D: Consider generalizations of the problem, such as several levels of interference or irregular transmitter placements. What other factors may be important to consider?
Requirement E: Write an article (no more than 2 pages) for the local newspaper explaining your findings
MCM2000
问题A 空间交通管制
为加强安全并减少空中交通指挥员的工作量，联邦航空局(FAA)考虑对空中交通管制系统添加软件，以便自动探测飞行器飞行路线可能的冲突，并提醒指挥员。为完成此项工作，FAA的分析员提出了下列问题。
要求A: 对于给定的两架空中飞行的飞机，空中交通指挥员应在什么时候把该目标视为太靠近，并予以干预。
要求B: 空间扇形是指某个空中交通指挥员所控制的三维空间部分。给定任意一个空间扇形，我们怎样从空中交通工作量的方位来估量它是否复杂？当几个飞行器同时通过该扇形时,在下面情形所确定的复杂性会达到什么程度：（1）在任一时刻？（2）在任意给定的时间范围内？（3）在一天的特别时间内？在此期间可能出现的冲突总数是怎样影响着复杂性来的？
提出所添加的软件工具对于自动预告冲突并提醒指挥员，这是否会减少或增加此种复杂性？
在作出你的报告方案的同时，写出概述（不多于二页）使FAA分析员能提交给FAA当局Jane Garvey ，并对你的结论进行答辩。

问题B 无线电信道分配
我们寻找无线电信道配置模型.在一个大的平面区域上设置一个传送站的均衡網絡,以避免干扰.一个基本的方法是将此区域分成正六边形的格子(蜂窝状),如图1.传送站安置在每个正六边形的中心点.
容许频率波谱的一个区间作为各传送站的频率.将这一区间规则地分割成一些空间信道,用整数1,2,3,…来表示.每一个传送站将被配置一正整数信道.同一信道可以在许多局部地区使用,前提是相邻近的传送站不相互干扰. 根据某些限制设定的信道需要一定的频率波谱,我们的目标是极小化频率波谱的这个区间宽度.這可以用跨度这一概念.跨度是某一个局部区域上使用的最大信道在一切滿足限制的配置中的最小值.在一个获得一定跨度的配置中不要求小于跨度的每一信道都被使用.
令s为一个正六边形的一侧的长度.我们集中考虑存在两种干扰水平的一种情况.
要求A: 频率配置有几个限制,第一,相互靠近的两个传送站不能配给同一信道.第二,由于波谱的传播,相互距离在2s內的传送站必须不配给相同或相邻的信道,它们至少差2.在這些限制下,关于跨度能说些什么.
要求B: 假定前述图1中的格子在各方向延伸到任意远,回答要求A.
要求C: 在下述假定下,重复要求A和B.更一般地假定相互靠近的传送站的信道至少差一个给定的整数k,同时那些隔开一点的保持至少差1.关于跨度和关于设计配置的有效策略作为k的一个函数能说点什么.
要求D: 考虑问题的一般化,比如各种干扰水平,或不规则的传送站布局.其他什么因素在考虑中是重要的.
要求E: 写一篇短文(不超过两页)给地方报纸,阐述你的发现.

MCM1999
Problem A Deep Impact

For some time, the National Aeronautics and Space Administration(NASA) has been considering the consequences of a large asteroid impact on the earth. As part of this effort, your team has been asked to consider the effects of such an impact were the asteroid to land in Antarctica. There are concerns that an impact there could have considerably different consequences than one striking elsewhere on the planet.
You are to assume that an asteroid is on the order of 1000 m in diameter, and that it strikes the Antarctic continent directly at the South Pole.
Your team has been asked to provide an assessment of the impact of such an asteroid. In particular, NASA would like an estimate of the amount and location of likely human casualties from this impact, an estimate of damage done to the food production regions in the oceans of the southern hemisphere, and an estimate of possible coastal flooding caused by large-scale melting of the Antarctic polar ice sheet.

Problem B Unlawful Assembly
Many public facilities have signs in room for public gatherings which state that it is "unlawful" for the rooms to be occupied by more than a specified number of people. Presumably, this number is based on the speed with which people in the room could be evacuated from the room' exits in case of an emergency. Similarly, elevators and other facilities often have "maximum capacities" posted
Develop a mathematical model for deciding what number to post on such a sign as being the "lawful capacity". As part of your solution discuss criteria, other than public safety in the case of a fire or other emergency, that might govern the number of people considered "unlawful" to occupy the room (or space).Also, for the model that you construct, consider the differences between a room with movable furniture such as a cafeteria (with tables and chairs), a gymnasium, a public swimming pool,and a lecture hall with a pattern of rows and aisles. You may wish to compare and contrast what might be done for a variety of differ
environments: elevator, lecture hall, swimming pool, cafeteria, or gymnasium. Gatheri such as rock concerts and soccer tournaments may present special conditions.
Apply your model to one or more public facilities at your institution (or neighboring town).Compare your results with the stated capacity, if one is post If used, your model is likely to be challenged by parties with interests in creasing the capacity. Write an article for the local newspaper defending you analysis.

MCM1999

问题A 强烈的碰撞

美国国家航空和航天局（NASA）从过去某个时间以来一直在考虑一颗大的小行星撞击地球会产生的后果。
　　作为这种努力的组成部分，要求你们队来考虑这种撞击的后果，加入小行星撞击到了南极洲的话。人们关心的是撞到南极洲比撞到地球的其它地方可能会有很不同的后果。
　　假设小行星的直径大约为1000米，还假设它正好在南极与南极洲大陆相撞。
　　要求你们对这样一颗小行星的撞击提供评估。特别是，NASA希望有一个关于这种撞击下可能的人类人员伤亡的数量和所在地区的估计，对南半球海洋的食物生产的破坏的估计，以及由于南极洲极地冰岩的大量融化造成的可能的沿海岸地区的洪水的估计。

问题B 非法的集会

　　在许多公众设施的用于公众集会的房间里都有指示牌，指明在本室的人员超过指定数目，那将是非法的，这个指定的数目可能室根据一有紧急情况时能从房间出口撤离的速度来确定的。类似地，在电梯和其他设施中常有“最大容量”之类地张贴告示。
　　试研制一个数学模型：什么数目可以作为“合法地容量”张贴在指示牌上。作为你们的求解的一部分，你们要讨论与火警或其他紧急情况不通的决定房间（或空间）中的人数为“非法”的准则。还有，你们构造的模型要考虑在诸如（带有桌、椅的）自助餐厅那样带有可移动家具的房间、体育馆、游泳池，以及有成排作为和走道的报告厅之间的差别。你们可能希望对比在各种不同的环境－电梯、报告厅、游泳池、自助餐厅和体育馆－下可能得出的结论的相似之处或不通之处。收集诸如摇滚音乐会和足球比赛那些能提出特特定条件的数据。把你们的模型应用与你们学院（或邻镇）的一个或多个公众设施。试把你们的结果和这些设施所指示的容量（如果有张贴的话）进行比较。如果用了后，你们的模型看来会引起提高容量的当事人的兴趣的话，试给当地的报纸写一篇捍卫你们分析的文章。

MCM1998
Problem A

Introduction:
Industrial and medical diagnostic machines known as Magnetic Resonance Imagers (MRI) scan a three-dimensional object such as a brain, and deliver their results in the form of a three-dimensional array of pixels. Each pixel consists of one number indicatin