<< . .

. 4
( : 20)



. . >>

kind of questioning, for example, if we had a list of all the possibilities
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

<< . .

. 4
( : 20)



. . >>