and were allowed to ask “Is it in the ¬rst half?” and, if the answer is

yes, then “Is it in the ¬rst one-fourth?”, etc. In practice we ordinarily

do not have such a list, and we can only approximate this procedure.

Example 3.3 In the familiar radio game of twenty questions it is not

unusual for a contestant to try to carry out a partitioning of the above

kind. For example, he or she may know that he or she is trying to guess

a city. He or she might ask, “Is the city in North America?” and if the

answer is yes, “Is it in the United States?” and if yes, “Is it west of

the Mississippi?” and if no, “Is it in the New England states?”, etc. Of

course, the above procedure does not actually divide the possibilities

exactly in half each time. The more nearly the answer to each question

comes to dividing the possibilities in half, the more certain one can be

of getting the answer in twenty questions, if there are at most a million

™¦

possibilities.

Exercises

1. If U is the set of integers from 1 to 6, ¬nd the cross-partitions of

the following pairs of partitions

(a) [{1, 2, 3}, {4, 5, 6}] and [{1, 4}, {2, 3, 5, 6}].

[Ans. [{1}, {2, 3}, {4}, {5, 6}].]

(b) [{1, 2, 3, 4, 5}, {6}] and [{1, 3, 5}, {2, 6}, {4}].

2. A coin is thrown three times. List the possibilities according to

which side turns up each time. Give the partition formed by

36 CHAPTER 3. PARTITIONS AND COUNTING

putting in the same cell all those possibilities for which the same

number of heads occur.

3. Let p and q be two statements with truth set P and Q. What

˜ ˜

can be said about the cross-partition of [P, P ] and [Q, Q] in the

case that

(a) p implies q.

˜

[Ans. P © Q = ….]

(b) p is equivalent to q.

(c) p and q are inconsistent.

4. Consider the set of eight states consisting of Illinois, Colorado,

Michigan, New York, Vermont, Texas, Alabama, and California.

(a) Show that in three “yes” or “no” questions one can identify

any one of the eight states.

(b) Design a set of three “yes” or “no” questions which can be

answered independently of each other and which will serve

to identify any one of the states.

5. An unabridged dictionary contains about 600,000 words and 3000

pages. If a person chooses a word from such a dictionary, is it

possible to identify this word by twenty “yes” or “no” questions?

If so, describe the procedure that you would use and discuss the

feasibility of the procedure. (One approach is the following. Use

12 questions to locate the page, but then you may need 9 questions

to locate the word.)

6. Jones has two parents, each of his or her parents had two parents,

each of these had two parents, etc. Tracing a person™s family tree

back 40 generations (about 1000 years) gives Jones 240 ancestors,

which is more people than have been on the earth in the last 1000

years. What is wrong with this argument?

7. Let [A1 , A2 , A3 ] and [B1 , B2 ] be two partitions. Prove that the

cross-partition of the two given partitions really is a partition,

that is, it satis¬es requirements (1) and (2) for partitions.

37

3.1. PARTITIONS

8. The cross-partition formed from the truth sets of n statements

has 2n cells. As seen in Chapter ??, the truth table of a state-

ment compounded from n statements has 2n rows. What is the

relationship between these two facts?

9. Let p and q be statements with truth sets P and Q. Form the

˜˜ ˜˜

partition [P © Q, P © Q, P © Q, P © Q]. State in each case below

which of the cells must be empty in order to make the given

statement a logically true statement.

(a) p ’ q

(b) p ” q

(c) p ∨ ¬p

(d) p

10. A partition [A1 , A2 , . . . , An ] is said to be a re¬nement of the par-

tition [B1 , B2 , . . . , Bm ] if every Aj is a subset of some Bk . Show

that a cross-partition of two partitions is a re¬nement of each of

the partitions from which the cross-partition is formed.

11. Consider the partition of the people in the United States deter-

mined by classi¬cation according to states. The classi¬cation ac-

cording to county determines a second partition. Show that this

is a re¬nement of the ¬rst partition. Give a third partition which

is di¬erent from each of these and is a re¬nement of both.

12. What can be said concerning the cross-partition of two partitions,

one of which is a re¬nement of the other?

13. Given nine objects, of which it is known that eight have the same

weight and one is heavier, show how, in two weighings with a pan

balance, the heavy one can be identi¬ed.

14. Suppose that you are given thirteen objects, twelve of which are

the same, but one is either heavier or lighter than the others.

Show that, with three weighings using a pan balance, it is possible

to identify the odd object. (A complete solution to this problem

is given on page 42 of Mathematical Snapshots, second edition,

by H. Steinhaus.)

15. A subject can be completely classi¬ed by introducing several sim-

ple subdivisions and taking their cross-partition. Thus, courses

38 CHAPTER 3. PARTITIONS AND COUNTING

in college may be partitioned according to subject, level of ad-

vancement, number of students, hours per week, interests, etc.

For each of the following subjects, introduce ¬ve or more par-

titions. How many cells are there in the complete classi¬cation

(cross-partition) in each case?

(a) Detective stories.

(b) Diseases.

16. Assume that in a given generation x men are Republicans and y

are Democrats and that the total number of men remains at 50

million in each generation. Assume further that it is known that

20 per cent of the sons of Republicans are Democrats and 30 per

cent of the sons of Democrats are Republicans in any generation.

What conditions must x and y satisfy if there are to be the same

number of Republicans in each generation? Is there more than

one choice for x and y? If not, what must x and y be?

[Partial Ans. There are 30 million Republicans.]

17. Assume that there are 30 million Democratic and 20 million Re-

publican men in the country. It is known that p per cent of the

sons of Democrats are Republicans, and q per cent of the sons

of Republicans are Democrats. If the total number of men re-

mains 50 million, what condition must p and q satisfy so that the

number in each party remains the same? Is there more than one

choice of p and q?

3.2 The number of elements in a set

The remainder of this chapter will be devoted to certain counting prob-

lems. For any set X we shall denote by n(X) the number of elements

in the set.

Suppose we know the number of elements in certain given sets and

wish to know the number in other sets related to these by the opera-

tions of unions, intersections, and complementations. As an example,

consider the following problem.

Suppose that we are told that 100 students take mathematics, and

150 students take economics. Can we then tell how many take either

mathematics or economics? The answer is no, since clearly we would

39

3.2. THE NUMBER OF ELEMENTS IN A SET

Figure 3.1: ™¦

also need to know how many students take both courses. If we know

that no student takes both courses, i.e., if we know that the two sets

of students are disjoint, then the answer would be the sum of the two

numbers or 250 students.

In general, if we are given disjoint sets A and B, then it is true that

n(A∪B) = n(A)+n(B). Suppose now that A and B are not disjoint as

˜

shown in Figure 3.1. We can divide the set A into disjoint sets A © B

˜

and A © B. Similarly, we can divide B into the disjoint sets A © B and

A © B. Thus,

˜

n(A) = n(A © B) + n(A © B),

˜

n(B) = n(A © B) + n(A © B).

Adding these two equations, we obtain

˜ ˜

n(A) + (B) = n(A © B) + n(A © B) + n(A © B) + 2n(A © B).

˜ ˜

Since the sets A © B, A © B, and A © B are disjoint sets whose union

is A ∪ B, we obtain the formula

n(A ∪ B) = n(A) + n(B) ’ n(A © B),

which is valid for any two sets A and B.

Example 3.4 Let p and q be statements relative to a set U of logical

possibilities. Denote by P and Q the truth sets of these statements.

The truth set of p ∨ q is P ∪ Q and the truth set of p § q is P © Q. Thus

the above formula enables us to ¬nd the number of cases where p ∨ q is

true if we know the number of cases for which p, q, and p § q are true.

™¦

40 CHAPTER 3. PARTITIONS AND COUNTING

Figure 3.2: ™¦

Example 3.5 More than two sets. It is possible to derive formulas for

the number of elements in a set which is the union of more than two

sets (see Exercise 6), but usually it is easier to work with Venn dia-

grams. For example, suppose that the registrar of a school reports the

following statistics about a group of 30 students: l9 take mathematics.

17 take music. 11 take history. 12 take mathematics and music. 7 take

history and mathematics. 5 take music and history. 2 take mathemat-

ics, history, and music. We draw the Venn diagram in Figure 3.2 and

¬ll in the numbers for the number of elements in each subset working

from the bottom of our list to the top. That is, since 2 students take

all three courses, and 5 take music and history, then 3 take history and

music but not mathematics, etc. Once the diagram is completed we

can read o¬ the number which take any combination of the courses.

For example, the number which take history but not mathematics is

™¦

3 + 1 = 4.

Example 3.6 Cancer studies. The following reasoning is often found

in statistical studies on the e¬ect of smoking on the incidence of lung

cancer. Suppose a study has shown that the fraction of smokers among

those who have lung cancer is greater than the fraction of smokers

among those who do not have lung cancer. It is then asserted that the

fraction of smokers who have lung cancer is greater than the fraction

of nonsmokers who have lung cancer. Let us examine this argument.

Let S be the set of all smokers in the population, and C be the

41

3.2. THE NUMBER OF ELEMENTS IN A SET

Figure 3.3: ™¦

˜

set of all people with lung cancer. Let a = n(S © C), b = n(S © C),

˜ ˜˜

c = n(S © C) and d = n(S © C), as indicated in Figure 3.3. The

fractions in which we are interested are

a c a b

p1 = , p2 = , p3 = , p4 = ,

a+b c+d a+c b+d

where p1 is the fraction of those with lung cancer that smoke, p2 the

fraction of those without lung cancer that smoke, p3 the fraction of

smokers who have lung cancer, and p4 the fraction of nonsmokers who

have cancer.

The argument above states that if p1 > p2 , then p3 > p4 . The

hypothesis,

a c

>

a+b c+d

is true if and only if ac + ad > ac + bc, that is, if and only if ad > bc.

The conclusion

a b

>

a+c b+d

is true if and only if ab + ad > ab + bc, that is, if and only if ad > bc.

Thus the two statements p1 > p2 and p3 > p4 are in fact equivalent

™¦

statements, so that the argument is valid.

Exercises

1. In Example 3.5, ¬nd

(a) The number of students that take mathematics but do not

take history.

42 CHAPTER 3. PARTITIONS AND COUNTING

[Ans. 12.]

(b) The number that take exactly two of the three courses.

(c) The number that take one or none of the courses.

2. In a chemistry class there are 20 students, and in a psychology

class there are 30 students. Find the number in either the psy-

chology class or the chemistry class if

(a) The two classes meet at the same hour.

[Ans. 50.]

(b) The two classes meet at di¬erent hours and 10 students are

enrolled in both courses.

[Ans. 40.]

3. If the truth set of a statement p has 10 elements, and the truth

set of a statement q has 20 elements, ¬nd the number of elements

in the truth set of p ∨ q if

(a) p and q are inconsistent.

(b) p and q are consistent and there are two elements in the

truth set of p § q.

4. If p is a statement that is true in ten cases, and q is a statement

that is true in ¬ve cases, ¬nd the number of cases in which both

p and q are true if p ∨ q is true in ten cases. What relation holds

between p and q?

5. Assume that the incidence of lung cancer is 16 per 100,000, and

that it is estimated that 75 per cent of those with lung cancer

smoke and 60 per cent of those without lung cancer smoke. (These

numbers are ¬ctitious.) Estimate the fraction of smokers with

lung cancer, and the fraction of nonsmokers with lung cancer.

[Ans. 20 and 10 per 100,000.]

6. Let A, B, and C be any three sets of a universal set U . Draw a

Venn diagram and show that

n(A ∪ B ∪ C) = n(A) + n(B) + n(C)

’n(A © B) ’ n(A © C) ’ n(B © C)

+n(A © B © C).

43

3.2. THE NUMBER OF ELEMENTS IN A SET

7. Analyze the data given below and draw a Venn diagram like that

in Figure 3.2. Assuming that every student in the school takes

one of the courses, ¬nd the total number of students in the school.

(a) First case:

28 students take English.

23 students take French.

23 students take German.

12 students take English and French.

11 students take English and German.

8 students take French and German.

5 students take all three courses.

(b) Second case:

36 students take English.

23 students take French.

13 students take German.

6 students take English and French.

11 students take English and German.

4 students take French and German.

1 students take all three courses.

(Comment on this result.)

8. Suppose that in a survey concerning the reading habits of students

it is found that:

60 per cent read magazine A; 50 per cent read magazine B; 50

per cent read magazine C; 30 per cent read magazines A and B;

20 per cent read magazines B and C; 30 per cent read magazines

A and C; 10 per cent read all three magazines.

(a) What per cent read exactly two magazines?

[Ans. 50.]

(b) What per cent do not read any of the magazines?

[Ans. 10.]

9. If p and q are equivalent statements and n(P ) = 10, what is

n(P ∪ Q)?

˜ ˜

10. If p implies q, prove that n(P ∪ Q) = n(P ) + n(Q).

44 CHAPTER 3. PARTITIONS AND COUNTING

11. On a transcontinental airliner, there are 9 boys, 5 American chil-

dren, 9 men, 7 foreign boys, 14 Americans, 6 American males, and

7 foreign females. What is the number of people on the plane?

[Ans. 33.]

Supplementary exercises.

˜

12. Prove that n(A) = n(U ) ’ n(A).

˜˜ ˜

13. Show that n(A © B) = n(A ∪ B) = n(U ) ’ n(A ∪ B).

14. In a collection of baseball players there are ten who can play

only out¬eld positions, ¬ve who can play only in¬eld positions

but cannot pitch, three who can pitch, four who can play any

position but pitcher, and two who can play any position at all.

How many players are there in all?

[Ans. 22.]

15. Ivyten College awarded 38 varsity letters in football, 15 in bas-

ketball, and 20 in baseball. If these letters went to a total of 58

men and only three of these men lettered in all three sports, how

many men received letters in exactly two of the three sports?

[Ans. 9.]

16. Let U be a ¬nite set. For any two sets A and B de¬ne the “dis-

˜ ˜

tance” from A to B to be d(A, B) = n(A © B) + n(A © B).

(a) Show that d(A, B) ≥ 0. When is d(A, B) = 0?

(b) If A, B, and C are nonintersecting sets, show that

d(A, C) ¤ d(A, B) + d(B, C).

(c) Show that for any three sets A, B, and C

d(A, C) ¤ d(A, B) + d(B, C).

45

3.3. PERMUTATIONS

Figure 3.4: ™¦

3.3 Permutations

We wish to consider here the number of ways in which a group of n

di¬erent objects can be arranged. A listing of n di¬erent objects in

a certain order is called a permutation of the n objects. We consider

¬rst the case of three objects, a, b, and c. We can exhibit all possible

permutations of these three objects as paths of a tree, as shown in

Figure 3.4. Each path exhibits a possible permutation, and there are

six such paths. We could also list these permutations as follows: abc,

bca, acb, cab, bac, cba. If we were to construct a similar tree for n

objects, we would ¬nd that the number of paths could be found by

multiplying together the numbers n, n ’ 1, n ’ 2, continuing down to