0.2 Discrete structures problem solving  (Page 6/6)

Understanding the Problem: This is a "find" type problem.

The problem is to obtain 6 quarts of water in the 9 quart pail using 4 quart and 9 quart pails as measures. You can fill either pail from the water source or from the other pail, and you can empty the pails any time.

Devising a Solution Plan: You can solve this in a number of different ways. Here we try "Working Backward" heuristic. It starts with the desired solution and work backward step by step. At each step we try to find a state that immediately precedes the current state such that we can reach the current state from that state with one simple operation such as filling a pail or emptying a pail in this problem. We repeat this process until we reach some easily reachable state such as empty pails, full pails, one pail full and the other empty, etc.

Our solution to the original problem is obtained by traversing this process backward to the desired state.

Let us denote the 9 quart pail by A and the 4 quart pail by B for simplicity. In this problem, the desired state is to have 6 qts in A (Figure 6).

As one can easily see if we could dump 3 qts from 9 qts in A, then we would have 6 qts in A. To be able to dump 3 qts from A we need 1 qt in B. Thus the state immediately preceding the current state is the one where A is full and B has 1 qt in it (Figure 7).

Thus first we fill up A. Then dump A into B leaving 5 qts in A (Figure 9). Then dump A into B again. This gives us 1 qt in A. Pour that into B. Then fill A and empty it into B. We now have 6 qts in A, which is what is required.

Example 6

Problem: A survey of TV viewers shows the following results:

To the question "Do you watch comedies?", 374 replied "Yes".

To the question "Do you watch sports?", 360 replied "Yes".

To the question "Do you watch detective stories?", 350 replied "Yes".

To the question "Do you watch comedies and sports?", 134 replied "Yes".

To the question "Do you watch comedies and detectives?", 96 replied "Yes".

To the question "Do you watch detectives and sports?", 241 replied "Yes".

To the question "Do you watch all three?", 37 replied "Yes".

Find the percentages of people who watch only comedies, only sports, only detective stories, comedies and sports, comedies and detectives, sports and detectives, and all three. By doing the same kind of analyses on the unknowns and data, one can find these percentages. The total number of people who watch at least one of these programs is

    374 + 360 + 350 - 134 - 96 - 241 + 37 = 650,

because each of 134, 96 and 241 is counted twice into 374 + 360 + 350, and 37 is counted in three times and subtracted out three times in 374 + 360 + 350 - 134 - 96 - 241.

Similarly the number of those watching only comedies is

    374 - 134 - 96 + 37 = 181,

the number of those watching only detectives is

    350 - 241 - 96 + 37 = 50,

the number of those watching only sports is

    360 - 134 - 241 + 37 = 22,

the number of those watching only comedies and detectives is

    96 - 37 = 59,

the number of those watching only comedies and sports is

    350 - 37 = 313,

the number of those watching only detectives and sports is

    241 - 37 = 204.

The calculation of the percentages is omitted.

Example 7

300 people were surveyed on TV programs they watch and all 300 responded. 75 of them say they watch a regular sports program, 210 say they watch a regular comedy program, and 36 say they watch both. There is a special detective story program which conflicts with the regular sports and comedy programs. If those who watch regular programs do not want to miss them, how many people can watch the special?

To answer the question, all you have to do is to find the total number of people who watch at least one of the regular sports and comedy programs. Then 300 minus that number is the answer. Thus this problem is essentially the same as Example 1, and the answer is 300 - (75 + 210 - 36) = 51.

Example 8

300 people were surveyed. 50 of them watch sports, 140 watch comedies, and 134 do not watch either of them. Then how many of them watch both comedies and sports? The relationships among various groups of people in this problem are the same as those of Example 1 or 7. Only the data are slightly different.

Since 300 were surveyed and 134 do not watch either sports or comedies, 166 watch at least one. Hence 50 + 140 - 166 = 24 watch both. Thus 50 - 24 = 26 watch only sports, and 140 - 24 = 116 watch only comedies.

Reference

Polya: G. Polya, How to Solve It, A New Aspect of Mathematical Method , Second Ed., Princeton University Press, Princeton, NJ, 1985. Larson: L. C. Larson, Problem-Solving Through Problems, Springer-Verlag, New York, NY, 1983.