Chapter 2

Three Basic Themes: Counting, Estimation, and Structuring

2.1. Introduction

THREE of the most powerful methods which play a prominent role in modeling are counting, estimation , and structuring. If a problem involves some finite set S , we often have to know exactly how many elements S contains, that is, we need to count the elements of S. One may count objects either directly through one-to-one correspondence or by means of relations which may exist between elements or sets. Estimation, on the other hand, is an art which improves with the amount of knowledge one has and which involves common sense based on a good use of the available facts. Estimation often serves as a basis for selecting models and orienting the direction of research: it may include the selection of reasonable upper and lower bounds or an acceptable range of values for the variable under consideration. We also include some examples of counting and estimation in a probabilistic setting. Structuring involves the seizing of some essential innate feature of the situation and then modeling the problem with respect to that feature. We close the chapter by looking at some common methods of proof which may be used in solving problems.

In Chapter 1 we discussed methods of modeling. We now turn our attention to results obtained using these methods.

We have already made brief mention of the type of outcome or result to be expected from a model. For example, we may obtain a number as an answer to a problem of “how many” or “how much;” we may find an upper or lower bound on a number; we may also obtain a function or a structure from which the solution may be derived. In fact, the number of forms which an answer may take is limited and an individual interested in modeling should be familiar with all of them. In this chapter we illustrate a large number of such results or outcomes by pursuing them through models constructed for the purpose of solving a problem. If one is familiar with how results are derived from models by appropriate manipulation, it becomes less pressing to solve every problem which may be encountered in modeling. This is, of course, an oversimplification of the diversity of results obtained from models (one may argue that no two problems are quite the same); still it seems obvious that with care the teaching of modeling would benefit greatly in time saved by not solving every problem completely but by concentrating on familiarization with many different types of models.

In addition to counting and enumeration, and estimating upper and lower bounds, we also have problems which involve finding maxima and minima (Chapter 4 ), and computing probabilities, expected values, and deviations (Chapter 5 ). Numbers are also used to assign ranks to objects and to obtain numerical priorities or to establish a sequential order in which they should occur. Other common forms which mathematical models may take are algebraic structures: (i) equations (Chapter 3 ) which can be used to obtain unknown numbers or functions; (ii) inequalities which may be used to establish bounds; and (iii) optimization methods (Chapter 4 ) used to locate maxima and minima as numbers or functions. Functions are used to describe relations and may be analytical, geometric, or tabular in form. Examples of more abstract algebraic structures which have found their way into applications are groups and lattices.

Another common form which a mathematical model may take is a geometric structure. Many problems formulated in a geometric setting such as those in Euclidean space can be translated into an algebraic setting, but there are others that cannot. Among these are problems in graph theory, geometric number theory, discrete geometry, and the geometry of numbers. Both algebraic and geometric structures are used to analyze conditions for the stability or instability of equilibrium of a system and to study other aspects of its behavior such as periodic oscillations or interaction with other systems. When a problem cannot be solved in one “whole” step it can often, by relaxing the original assumptions, be decomposed to obtain partial solutions, i.e., the problem can be decomposed into components and each solved in a partial step. The whole step solution is then composed of these “partial” steps either by simply combining the steps in a static composition of the partial solutions or by carrying out transformations in the model from step to step in such a way as to leave the “partial”-step solutions invariant in a dynamic composition of these solutions.

These examples cover a wide range of “results” which constitute a basis for constructing models to improve understanding, to predict, and to solve problems. Many other types of results will be found throughout the book.

2.2. Counting

As we have already noted, we frequently need an organized method of counting: an answer to the questions How many? or How much?

We start with a simple problem.

Example 1. A Simple Inventory Problem

We have an initial stock of X units of an item with a deterioration rate per year of L per unit. We use D items for stock at the end of the year. How much is left at the end of n years?

At the beginning of the first year we have X units.

At the end of the first year we have

At the end of the second year we have

At the end of the third year we have

and at the end of the n th year we have

This is the desired amount of stock left after n years. This process must terminate for that value of n which makes the remainder, before removal of D , less than D , i.e. for the value of n which first makes our expression above negative.

For example, let X = 1000, L = 0.2, D = 100. Then the stock after n years is given by

It is equal to 700 for n = 1; 460 for n = 2; 268 for n = 3; and 114.4 for n = 4. For n = 5 deterioration reduces the stock to less than 100 items, so the process will terminate.

We now consider three examples in which we calculate bounds for a required number: these bounds may or may not be attained.

Example 2. The Number of Cherries in a Can

We are often faced with estimating the maximum number of objects contained in a container, particularly when we are designing the container and the possible arrangement of the objects in the container. The following is a simple illustration of this.

How many cherries each of radius r can be packed in a can of radius R and height h ? This will vary with the packing, so we obtain upper and lower bounds and refine them as far as possible. For example, no more cherries than the ratio of the volume of the can to that of a cherry can be packed in the can. A finer upper bound is obtained by multiplying the volume of the can by 0.74, the greatest known density for packing spheres, and then dividing the result by the volume of a cherry. As a lower bound we may first see how many circles of radius r can be packed in a circle of radius R. We then divide the height of the can by 2r ; the integral part of this ratio gives us the maximum number of layers of cherries. The product of these two quantities gives a lower bound.

Example 3. Family Tree and Counting Trees

This example illustrates the “essential brotherhood” of man. Let H be your family tree and let n be the number of generations represented in H . How large must n be so that sufficiently far back in time two branches of the family tree meet in the same ancestor? The population of the world today is approximately 4.5 × 109 . We assume that the population of the world n generations ago was not more than 4.5 × 109 . Now one individual living today descended from two individuals. They each in turn descended from two other individuals, and n generations ago the tree would have had 2n individuals at that generation level. These can be distinct only if 2n ≤ 4.5 × 109 . Hence if 2n ≥ 4.5 × 109 the individuals could not be distinct, and two branches would have the same ancestor. If 2n = 4.5 × 109 , then n is approximately equal to 32. Thus an upper bound to the number of generations we need to go back to find a common ancestor is 32.

We conclude this section with our final upper bound example.

Example 4. Length of a Path Containing n Points

We are often concerned with minimizing the distance travelled through a number of places. There is a long standing problem in the field of operations research called the traveling salesman problem (yet unsolved) which has the same concern in that the salesman must visit n cities traveling the shortest distance. The exact answer to this problem as formulated here in the Euclidean plane is not known but here is a good bound.

Given any n (≥ 2) points in a unit square, there is a path through the n points which does not exceed (2n )1/2 + 1.75 in length. [Few.]

Consider the unit square 0 ≤ x ≤ 1, 0 ≤ y ≤ 1, and let the coordinates of the n points be (x 1 , y 1 )…(x n , y n ). Consider q horizontal lines y = 0, 1/q , 2/q ,…, 1, with q arbitrary, and draw from each of the n points a perpendicular to the nearest of the q + 1 lines (Fig. 2.1 ). Repeat the construction, using the q lines, y = 1/2q , 3/2q ,…, (2q – 1)/2q .

FIG . 2.1.

Each construction gives a path consisting of suitable portions of the lines, x = 0, 0 ≤ y ≤ 1, and x = 1, 0 ≤ y ≤ 1, together with each perpendicular line counted twice—once from a horizontal line to a point and then back to the horizontal line—thus continuing the path through the n points. If we denote these two paths by L 1 and L 2 , respectively, we have

where ||α|| denotes the absolute difference between α and the nearest integer. Note that

We have

We choose the integer q to minimize this value: it is the integer nearest to (n /2)1/2 . Thus n = 2(q + θ )2 , with |θ | ≤ . Substituting for n , we have

Consequently the length of one of the two paths does not exceed (2n )1/2 + 1.75.

2.3. Results of Estimation

We have considered exact counting and upper and lower bounds to values of interest to us. We now move on to estimation, where we need a very approximate idea of size. As we have already noted, we use “estimation” in its everyday rather than in its statistical sense.

We often want a very rough approximation to a result in order to determine feasibility and practicality. Frequently our concern is simply to obtain an order of magnitude.

The following three examples illustrate these ideas.

Example 1. Chess Strategies

How many strategies are open to each player in a game of chess?

How long would it take a computer to analyze a game?

We consider the middle game. In general, White and Black will each have about 30 to 40 legal moves available. Combining each legal move of White with each legal move of Black gives about 1000 possible combinations of a single move of each player. Two consecutive moves would lead to a million different positions, three moves to a billion, four moves to a trillion and so on, multiplying the number of possible variations by 1000 each time a move is made.

A good chess game between evenly matched players averages from 40 to 50 moves. Since each new move generates 1000 possible combinations and each one must be combined with the 1000 variations of the next move, it follows that 25 moves each would generate a total of 1075 variations. Assume that a computer can analyze a million variations per second; it would take the computer 1069 sec to decide which move to make next.

How long is 1069 sec? Well, our planetary system is estimated to be 4 billion years old, which in round numbers is 1018 sec.

This example leads us to the conclusion that a chess-playing computer should not try brute-force exhaustive analysis of the next 25, or even of the next 10, moves. Instead, it should probably follow the experts and depend upon positional analysis and tactical maneuvering, letting long-term strategy take care of itself.

The next example deals with astronomical distances, where we are often satisfied with order of magnitude approximations.

Example 2. The Diameter of the Observable Universe [Asimov]

We are concerned with estimating the size of the observable universe.

Hubble's law states that the velocity of recession of a galaxy varies directly with its distance from the earth. Thus, we may “reach” a point where a galaxy is receding from us at the speed of light and in consequence nothing from that galaxy or points beyond can be observed by us. The problem is to estimate this distance and hence the diameter of the observable universe.

By Hubble's law [1]

where V is the velocity of recession in miles/sec, D , is the distance from the earth in millions of light years, and k is Hubble's constant.

To find k , we use the following information. The Virgo cluster is receding from us at 710 miles/sec, as shown by the red shift of its components. The brightness of the Virgo cluster when compared with the brightness of the Andromeda galaxy shows that it is 16.5 times as far away as the Andromeda galaxy, which is 2,300,000 light years away.

Thus for Virgo,

Therefore k = 710/38 = 18.5. Some recent calculations suggest that this is somewhat large. We assume that k = 15. Using V = 186,282 miles/sec (speed of light) gives

Consequently, the limit of observation is 12,500 million light years away, or the diameter of the observable universe is 25 billion light years.

The next example relates to information theory. In that field a bit is defined as a unit of computer memory corresponding to the ability to store the result of a choice between two equally probable alternatives.

Example 3. Brain Storage

Here we estimate the upper limit of the amount of information that the human mind can handle. An individual cannot give his full attention all the time, but if he could and if he were able to handle 20 bits of information per second (recall that this means 220 ≈ 1,000,000 different possibilities per second) then over a 14-hour day he would handle 106 bits. Over 50 years this would become over 1010 bits or 210 10 possibilities. Even so, he would not need the total capacity of his nervous system to store this information. Consider that there are 1010 neurons in the human brain and 1012 interneuron connections or synapses so that the number of possible networks which can be formed from the neurons and available synapses is a very large number. Only a small number of the available cells is necessary for storage.

The French physicist J. C. Levy has shown that only one millionth of the available cells would be required to store the amount of information we are discussing. We can also note that a man can retrieve 5 × 1010 bits of information per second whereas a computer can retrieve 109 bits/sec: the computer is almost as efficient as a man in this respect.

2.4. Counting and Estimation and their use in Probability

Counting may arise in at least two ways in problems where probability is involved. One may have to calculate the number of ways in which something can happen (as in classical probability), or one may need the expected value of a quantity.

We have already noted that estimation can be used at a preliminary stage in model building; it can also be used later to give a rough check on whether a model which has been derived is reasonable. We use it here in a test of a probability model.

Example 1. Passenger Pick-up and Discharge Capacity

We need to know if there is adequate parking space for 600 cars each hour to discharge passengers at the curb of a 1000-ft frontage of the enplaning level of a new Pan-American terminal. A car occupies a space for about 102 sec. For a number of reasons, it is possible to provide only 28 parking spaces along this frontage. It is assumed that the cars arrive by a single lane into three-lane traffic at the frontage and that the right lane is used for parking, the middle lane for maneuvering, and the left lane for movement.

If we assume that the left lane moves at 5 mph, while cars move into and out of it, and that each car is 17 ft long, and if we allow a car length between cars for each 10 mph, we must allow approximately 25 ft of space per car. In 1000 ft there is room for 40 cars in a single lane. At 5 mph it takes almost 2 min for a moving car to clear the frontage. Thus, in one hour, we can move through a single lane (without parking) at most (60 ÷ 5/2) × 40 = 960 cars, which is more than the 600 needed.

Now the service rate of a space is 3600/102 ≈ 35 cars per hour. Since there are 28 spaces, then 28 × 35 = 910 cars per hour may park, which is well in excess of the peak hour requirement of 600 and below the 960 which can move through the area. Of course we are assuming ideal conditions and intelligent parking. The analysis here is based on averages.

The exact analysis was based on a renewal model which was developed in the study and which confirmed the conclusion of the foregoing argument with a high probability.

The next problem involves counting outcomes, and uses a very nice method to accomplish this.

Example 2. The Box-office Cash Problem

There are 2n people lined up at a ticket office: n have only $5 bills; n have only $10 bills. The box office has no cash when it opens, and each customer will purchase one $5 ticket. What is the probability that no customer waits for change?

Here, a picture helps considerably. Locate each customer at the points 1, 2,…, 2n along the abscissa of an (x , y ) coordinate system in the order they appear in line; the box office is at the origin. To each person with a $10 bill, assign + 1; to each person with a $5 bill, assign – 1. As we move from left to right, the values assigned to the customers at the corresponding points are accumulated and plotted on the ordinate. Connecting these ordinates yields a trajectory for the given customer ordering. The trajectory always ends at the point (2n , 0) (Fig. 2.2 ).

FIG . 2.2.

There are trajectories (i.e., the number of ways of distributing n ascents among 2n ascents and descents). The x -axis represents the condition of no change at the box office, so any ascent above the x -axis represents the arrival of a customer with $10 when there is no change available; all such unfavorable trajectories must touch the line y = 1 at least once. To count these unfavorable outcomes, we construct a new trajectory as follows:

 (i) The new and old trajectories coincide up to the first point where y = 1 is touched.

(ii) From that point on, the new trajectory is a reflection of the old about the line y = 1 (see bold line in the figure). The new trajectory must end at (2 n , 2) because it will always involve a reflection of the point (2 n , 0) about the line y = 1. Thus, there are now two more ascents than descents to give a total of n + 1 ascents. Hence there are new trajectories and favorable (old) trajectories. The desired probability is [Gnedenko]

In the next example, we show how estimation may be used to determine abstract epistemological limits.

*Example 3. Processing Information [Bremermann]

Using ideas from quantum mechanics and information theory, Bremermann has posed the following conjecture: “No data-processing system whether artificial or living can process more than (2 × 1047 ) bits per second per gram of its mass.”

This bound has been widely discussed in the literature of cybernetics and general systems theory where it has acquired the name “the Bremermann limit.”

The proof is simple. Information must be represented by some kind of marker. Assume that energy levels are used as markers. Assume also that the levels must lie in an interval (0, E max ) and that the energy levels can be measured to accuracy ∆E . At most, one can distinguish

energy levels. The information obtained in measuring a random variable which can take on any of n values, each with probability p 1 …p n is

which takes on its maximum value when p 1 = p 2 =…p n = 1/n . This maximum is given by H max where

We consider how to divide up energy E max to maximize the information. For one marker (per instant) with n levels, there are n + 1 distinguishable marker values (counting 0) and, by (2.2 ),

Now consider two markers, each with energy levels in the range (0, E max ). Then a maximum of

bits can be represented with energy E max . The optimal use of the given amount of energy E max occurs with n markers with values in (0, ∆E ). Then

The maximum energy any self-contained computing system of mass m can utilize as a marker is given by Einstein's equation:

By Heisenberg's uncertainty principle, the accuracy of energy measurement is bounded in time ∆t by the relation

(∆E = energy uncertainty, ∆t = duration of measurement, h = Planck's constant.) Substituting (2.1 ) and (2.4 ) into (2.5 ) yields

and

which for (2.3 ) is the optimal energy usage.

Thus, since

we have the desired bound (per gram of mass m ) of 2 × 1047 bits/sec.

2.5. Structuring

Possibly the most important factor in modeling is the ability to grasp the essential structure of a problem or situation.

Our first example which is non-numerical refers to a popular puzzle: its solution involves decomposition into simple elements, and the invariance of essential properties under transformation.

Example 1. The Colored Cube Problem [Busacker and Saaty]

An illuminating illustration of a nice way to structure a problem is Instant Insanity. We are given four cubes, the faces of which are colored with one of four colors. Since there are six faces, each cube would have more than one face colored with the same color. The coloring of the cubes is different so two cubes are not necessarily colored the same way. The problem is to stack the cubes vertically in such a way that we have a rectangular prism and each of the rectangles on a side of the prism has all four colors appearing in it, not necessarily in the same order.

Of course, the problem may not have a solution. For example, if all three faces meeting at a corner of each cube are colored with the same color for all four cubes, then that color appears in the stack at least eight times instead of the required four; the problem has no solution.

Our first step is to represent the geometry of the problem by a plane figure. We draw four points as corners of a square letting each corner represent a different color, and we also label the cubes 1 to 4. Each cube has three pairs of opposite faces. We take the first cube and draw lines connecting the vertices associated with each pair of opposite faces and label these three lines with number 1. We do the same for each of the other three cubes. In all, we have 12 lines with three labeled 1, three labeled 2, etc. A possible representation is illustrated in Fig. 2.3 where the colors are labeled R, G, W, and B (for red, green, white and blue).

Next we decompose the problem into two parts: we solve the problem for one pair of opposite reactangles in the stacking and then for the other pair. We note that in each pair each cube is used once and each color appears twice, one in each rectangle. Thus, we draw the four points associated with the colors and choose four lines from the diagram that are labeled 1, 2, 3, 4 (thus each cube is used once) but in such a way that each point is incident with two lines. When this is done, the same procedure is repeated for the remaining pair of opposite rectangles. Adjustment in the choice of lines for the first pair of rectangles may be necessary to solve the problem for the second pair. The solutions for the two parts are independent. Given the solution of one partition, the other is obtained by a rotation around an axis passing through the centers of the two opposite faces of the cubes which appear in the first solution thus leaving it invariant. Figure 2.4(a) and (b) portrays these solutions corresponding to Fig. 2.3 . Note that to ensure the alternate appearance of each color in opposite rectangles one can proceed sequentially from one vertex to an adjacent vertex using the cubes in the order in which the edges travel but alternating the distribution of each color between the two opposite rectangles.

FIG . 2.3.

FIG . 2.4.

In the next example we use analytical structuring.

Example 2. The Stable Table [Saaty, 1972]

Consider a square table with four legs whose lengths are equal. Suppose that the ground is not a smooth, flat surface, but a wavy, humpy one (not too much relative to the length of the table's legs). Show that there is always a position where the table could stand so that each leg rests on the ground (i.e., the table has no wobble, although it may be tilted).

We note that it is always possible to stand the table so that three legs touch the ground: hold two legs up and tilt the table so that two legs touch the ground. Then put down the other two legs; one of them will touch first. Thus, there is always a pair of legs on one of the two diagonals which touches the ground. Let x be the sum of the heights of these legs above the ground. Since both of them touch the ground, we have x = 0. Let y be the sum of the heights of the two legs on the other diagonal (one of them contributes zero height because three legs always touch the ground). Let us rotate the table 90 degrees so that each diagonal goes into the other. Now x and y are functions of the angle of rotation θ , and we have

The last relation holds because three legs always touch the ground.

Consider the value of θ at which x (θ ) just changes from zero to positive. At that value y (θ ) must just turn zero. Thus, at that value of θ , both x and y vanish, and all four legs must rest on the ground.

The following example gives a way of structuring a situation so as to create stability. It shows that stability may be achieved by compromise. There are times when our best preference would cause us unhappiness.

Example 3. The Stability of a Set of Marriages [Gale and Shapley]

We consider n boys and n girls to be paired off in marriages: in this social situation we call such a set of marriages unstable if under it there is a boy or a girl who are not married to each other but prefer each other to their actual mates. Otherwise the set of marriages is called stable. The key structural ingredient in this example is the linear ordering by each person of his possible mates. This allows us to find an algorithm for the pairing-off process that produces a solution which is stable by its construction. Each girl (and each boy) ranks the boys (the girls) according to preference, and each boy proposes to his favourite girl. She keeps on a string, but does not yet accept, the man she most prefers. The rejected boys choose again according to their second preferences, etc., and each time the girl keeps on a string the boy she prefers most and releases any less-preferred suitors who may be already on her string. There are at most n 2 – 2n + 2 such attempts of proposal by all the boys to all the girls. No boy proposes to the same girl more than once. Hence, every girl gets a proposal. The process terminates when every girl has been chosen (which must obviously be the case). Then the girls accept these boys for marriage. These marriages are stable because if a boy prefers another girl to his wife then she does not prefer him because he would have proposed to her before proposing to his wife but she rejected him in favor of her husband.

We move back in time to the nineteenth century and the buffalo. Our next example involves algebraic structuring of a problem and yields numerical answers.

Example 4. Controlled Slaughter of Animals for Food [Truxal and David]

Between 1830 and 1887 the buffalo population in the United States was reduced from 40 million down to 200 heads. The average weight of a buffalo was about 1000 lbs, an amount of meat sufficient for at least five people for a year. The slaughter was carried out for parts of the animal; its tongue and its hide. In about 60 years, the lack of a policy for harvesting this potential source of food led to an almost complete destruction of the animal.

We know that 10% of the mature animals die each year, maturity is reached in two years, and 90% of the mature females have a calf a year. Of the total calves born, 53% are male and 47% are female. Because of high infant mortality, only 30% of the calves live to maturity.

It is desired to determine the number of beasts to be harvested each year. By controlling the female population, the number of new births is thereby determined. This enables us to estimate the percentage of beasts that should be harvested each year.

If we let F n denote the number of mature females at the start of year n , then since 10% die and p % are harvested, {0.9 – (p /100)}F n – 1 survive from year n – 1 to year n .

In addition, consider the number of mature females F n – 2 at the beginning of year n – 2: 90% of them give birth to calves of which 47% are female. Of this group of calves, 30% survive to maturity two years later. Thus these females in year n – 2 contribute 0.9 × 0.47 × 0.3 = 0.1269 new females to the female population at the beginning of year n . We thus have the following relation:

If it is desired to maintain the same number of mature females every year, F n = F n – 1 = F n – 2 giving p = 2.69%. If this rate had been applied to a population of 40 million males and females (more males can be harvested because there are more of them), more than a million could have been harvested each year, providing meat for at least five million people.

We now turn to a very powerful method for structuring problems, particularly in physics.

*Example 5. Dimensional Analysis [Bridgeman]

In physics, physical variables originate largely in the operations symbolized in their dimensional formulas. Dimensional formulas and equations have a structure closely related to the operations of physical measurement. A small number of variables is selected and all other variables may then be expressed as a function of the basic set.

Usually mass m , length l , time T , and electric charge Q are used as the fundamental, or primary, variables. A theorem in dimensional analysis asserts that any physical variable f is proportional to a product of powers of primary variables P 1 , P 2 ,…, P n ; that is, if a 1 , a 2 ,…, a n are rational numbers, then

where K is a proportionality constant. Frequently K is dropped and one writes where the brackets indicate dimensional equivalence.

For example, force may be expressed in terms of the primary variables given above as F = K (MLT –2 ).

As an illustration, suppose that it is required to calculate the period of a simple pendulum consisting of a rigid rod of length h supporting a mass m and having an angular displacement θ .

The functional expression for the physical variables involved is

or, dimensionally,

The equations obtained by equating corresponding powers are

Since we wish to take θ into account, we include an unknown function f (θ ) and write

Experimentally, one finds that, if θ is small, f (θ ) is almost constant and approximately 2π (assuming K = 1). Note that since the exponent of mass is zero the period is independent of the mass.

By similar arguments the reader will have no difficulty in verifying the well-known elementary relations of physics, s = gt 2 and v 2 = 2as , where s is distance, v is velocity, a is acceleration, and g is the acceleration due to gravity.

Dimensional analysis plays an important role in forming “order of magnitude” estimates of certain properties of physical systems. We give two illustrations.

(i) The Power in Wind

Suppose the wind blows with velocity V at a windmill whose area facing the direction of the wind is A. The only relevant physical constant we need is ρ , the density of air. The dimensions are:

The dimension of power P (energy × T – 1 ) is

(ii) Ship Size and Speed

A powerful illustration of the use of this method now follows.

Let a ship make a voyage, e.g., across the Atlantic at a speed V . Let L be the length of the ship, S its wet surface area, T its tonnage, D its displacement or volume, H its horsepower, R the resistance, and C the coal necessary for the voyage. It is known from experiments comparing two ships that L ∝ V 2 . If we double the length of a ship from L 1 = 1 to L 2 = 2, then the corresponding speeds satisfy V 1 2 /V 2 2 = 1/2. Now we have

Thus, if it is desired to increase the speed by 1%, the length must be increased by 2%, the displacement by 6%, the coal consumption by 6%, the horsepower and the necessary boiler capacity by 7%.

2.6. Proving

Many problems may be solved by proving or disproving a given hypothesis; this is one of the most common processes in mathematics.

In the legal field one is often concerned about being fair in judgment or division of assets. Here is a simple creative illustration of how to do fair division.

Example 1. Fair Division [Saaty, 1970]

How might one fairly divide a cake among three people so that each is satisfied with his share?

If there were two people only, one of them divides it and the other chooses his share first.

For three people, we let the first one divide the cake into three parts and ask the second to choose a piece which he keeps if the third person does not object on the ground that it is too large. If he objects, he is asked to cut this part into two parts of which the second chooses one and the third person takes the other. Of the two remaining parts, either both the second and the third agree on one piece which they divide or they each want to divide a different part with the first person. In either case, the problem is reduced to dividing a cake fairly between two people.

A common method of proof is that of mathematical induction. This requires that one must show that a given property holds for n = 1 and that whenever the property is assumed true for n = k it is also true for n = k + 1. The principle of induction then says that the property is true for all n . Prove by induction that .

Example 2. Acquaintances

Given six people, each of whom may or may not know any of the others, prove that there is always either a set of three people who know each other or three people none of whom knows the other two.

Suppose this statement is false; i.e., there are never three people who either do or do not know one another. Consider now any of the six and that person's relations with the other five. These relations involve knowing or not knowing each of them. Because there are five there will always be either at least three people whom he knows or three people whom he does not know. Suppose he knows at least three people and consider any three of them. Since the statement is assumed false, each of them must not know the other two, for otherewise, we would have a triangle of two of them and the original one with which we started, who know each other, which would contradict the assumption that the statement is false. Now, this group of three people who do not know each other violates the assumption that the statement is false. Thus, the assumption is itself false, and the statement must be true. A similar argument would apply if he did not know at least three people.

Note that the statement would not be true if we started out with five people: they might be represented as situated at the nodes of a pentagon, each connected to its two neighbors for acquaintance but to no other. It would not be possible in this situation to find the triangle in which three people know one another or do not know one another.

This result can also be placed in the context of graph theory. Let K n denote the graph consisting of n points and all the possible edges joining distinct pairs of points. No matter how we color the edges of K 6 using two colors, say red and blue, we find that there must be a triangle of edges all colored the same (such a triangle is called monochromatic ). (We can let the six points correspond to the six people with red lines to denote acquaintanceship and blue lines nonacquaintanceship.) It is suggested at this point that the reader draw a number of possible figures as illustrations of the situation. We can show what can happen for five people by drawing a blue five-pointed star and circumscribing a red pentagon. This drawing of K 5 has no monochromatic triangle.

This completes our introduction to the very fundamental topics of counting, estimation, and structuring. The references at the end of this chapter contain a wide variety of examples.

In our next chapter , we shall consider different types of equations and the ways in which they arise in modeling.

Chapter 2—Problems

1. What is the maximum number of pieces into which a circular pie can be cut with n straight cuts if no piece can be moved after any cut? Answer: (n 2 + n + 2)/2. (Hint : relate the number of pieces resulting from n cuts to those resulting from n – 1 cuts.)

2. Two missionaries and two cannibals wish to cross from the left to the right bank of a river by row boat. The boat can carry no more than two people at a time and must be brought back for the next crossing. At no time should there be more cannibals than missionaries, since the cannibals, from force of habit, would eat the outnumbered missionaries. How can the crossing take place? (Hint : represent the states on the left bank by (a, b ) where a is the number of missionaries b is the number of cannibals, and consider means of transition from (2, 2) to (0, 0). What transitions are possible? Can you draw a graph? Can you represent this graph by a matrix? Would it be simpler to solve this problem by trial and error? What would happen if the numbers were larger?)

3. We want to find the most efficient method of parking cars in a lot. How can we structure this problem? (Consider the simpler problem of packing circles in a plane so that any circle may be moved by sliding without disturbing any of the other circles.) For a full discussion of this problem, see Heppes.

4. Take the marriage stability example and translate it to the problem of multiple applications by n students to m colleges with m ≤ n . (Note that a college may accept more than one student.)

5. Telephoned orders are placed alphabetically according to the family name. There is thus a bias towards letters like S and when the order arrives there is more search to do under S. A new system uses the last two numbers of the customer's phone number. These are assumed to be random and hence would distribute the customers’ orders uniformly in the catalogue and could be accessed more rapidly. Can you propose two other ways for this purpose? What are other activities for which you have more systematic and efficient implementations?

6. Most theatres empty their audience in a matter of 10–15 min. You are standing at the door of a theatre observing the rate at which people exit. The theatre has four exit doors. Give a reasonable way to estimate the number of seats without going in.

7. How would you estimate the average number of hairs on a person's head?

8. Give a formula for estimating the number of uniform spherical cherries of a certain radius to be packed in a cylindrical can of given radius and height. How would you allow for space between cherries? Enter this in your model. Do this a second time with a different scheme.

9. Give an efficient, approximate hierarchical scheme for getting 10 people to count a stack of money consisting of about $1,000,000. (If all else fails, weight it.)

10. Use dimensional analysis to obtain an expression for the power which could be extracted per unit length of coastline facing the incoming sea. [Hint : The relevant dimensions include wavelength, period, the density of water, the amplitude and gravity.]

11. Given the number of digits D used in printing the page numbers of a text, determine the number of pages P in the text. For example, a text of 13 pages uses nine digits up to page 9 and two digits per page from pages 10 to 13 yielding a total of 17 digits. The problem here is to reverse this process. Show that

12. The classical counting problem known as the hat-check problem may be formulated as follows: n men walk into a bar, check their hats, and proceed to get drunk. They all leave together but, fumbling with their hat-checks, wind up drawing hats at random. Show that the probability that no man gets his own hat is

(Hint : let A n be the number of ways of distributing n hats among n men such that no one gets his own hat and P n be the corresponding probability. If (n – 1) men go through the process and end with no man having his own hat and if an n th man joins them with his hat then he can exchange it with any one of them. This gives (n – 1)A n – 1 ways. Further, if any one of them has his own hat, he can exchange it with the new man. This adds (n – 1)A n – 2 ways. There are no other possibilities. Thus A n = (n – 1)(A n – 1 + A n – 2 ). Also A i = i ! p i .)

13. Two diagonally opposite corner squares are cut out from a chess board. Is it possible to cover the remainder of the board with nonoverlapping dominos, each of which covers two squares? [Hint : Consider the color of the squares which are cut out.] Straddling the left most column and its neighboring column, there must be an odd number of dominos. Since the neighbor gets an odd number straddling it and its right neighbor there is also an odd number and so on. In all the number of horizontal dominos is odd. Similarly the number of vertical dominos is odd yielding an even total number. However, 31 is all that we need.

References

Asimov, Isaac, The Universe: From Flat Earth to Quasar , Walker, New York, 1966.

Bridgeman, P., Dimensional Analysis , Yale University Press, 1931.

Bremermann, H. J. Optimization through evolution and recombination, in Self-Organizing Systems (eds. M. C. Yovits, G. T. Jacobi, and G. D. Goldstein), Spartan Books (Washington DC, 1962), p. 93.

Busacker, Robert G. and Thomas L. Saaty, Finite Graphs and Networks , McGraw-Hill, New York, 1965.

Few, L., The shortest path and the shortest road through n points, Mathematika , Vol. II, 1955 pp. 141–144.

Gale, D. and L. S. Shapley, College admissions and the stability of marriage, Am. Math. Monthly , Vol. 69, No. 1, 1962.

Gnedenko, B. V., The Theory of Probability , Chelsea Publishing Co., New York, 1951.

Heppes, A., On the densest packing of circles not blocking each other, Stud. Sci. Math. Hung. , Vol. 2, No. 1–2, 1967 pp. 257–263.

Saaty, Thomas L., Optimization in Integers and Related External Problems , McGraw-Hill, New York, 1970.

Saaty, Thomas L., The Thinking Man's Joke Book Series , Vol. IV, G. & S. Publications, 1972.

Truxal, J. G. and E. E. David, Jr., Man and His Technology , Engineering Concepts Curriculum Project, McGraw-Hill, New York, 1971, 1973.

Bibliography

Berge, Claude, The Theory of Graphs and Its Applications , Wiley, New York, 1962.

Berge, Claude, Principles of Combinatorics , Academic Press, New York, 1971.

Cohen, M. R. and E. Nagel, An Introduction to Logic and Scientific Method , Harcourt, Bruce & Co., New York, 1934.

Courant, Richard and Herbert Robbins, What is Mathematics ?, Oxford University Press, 1941.

Feller, W., An Introduction of Probability Theory and Its Application , Vol. I, 2nd edn., Wiley, New York, 1957.

Landau, E., Foundations of Analysis , Chelsea Publishing Co., New York, 1951.

Liu, C. L., Introduction to Combinatorial Mathematics , McGraw-Hill, New York, 1968.

McMahon, Percy A., Combinatory Analysis , Vols. 1 and 2, Chelsea Publishing Co., New York, 1960.

Netto, E., Lehrbuch der Combinatorik , Chelsea Publishing Co., New York, 1901.

Parzen, Emanuel, Modern Probability Theory and Its Applications , Wiley, New York.

Riordan, J., An Introduction to Combinatorial Analysis , Wiley, New York, 1958.

Ryser, Herbert J., Combinatorial Mathematics , Wiley, New York, 1963.

Saaty, Thomas L., Mathematical Models of Arms Control and Disarmament , Wiley, New York, 1968.

Saaty, Thomas L., (ed. with F. J. Weyl), The Spirit and Uses of the Mathematical Sciences , McGraw-Hill, New York, 1969.