Page 402 - Discrete Mathematics and Its Applications

Supplementary Exercises 381

√
47. Is this proof that element a. Then show that a 2 − a is a smaller positive
1 1 1 3 1 integer of this form.]
+ + ··· + = − ,
1 · 2 2 · 3 (n − 1)n 2 n 52. A set is well ordered if every nonempty subset of this
set has a least element. Determine whether each of the
whenever n is a positive integer, correct? Justify your an-
swer. following sets is well ordered.
a) the set of integers
Basis step: The result is true when n = 1 because
b) the set of integers greater than −100
1 3 1 c) the set of positive rationals
= − .
1 · 2 2 1 d) the set of positive rationals with denominator less than
100
Inductive step: Assume that the result is true for n. Then
53. a) Show that if a 1 ,a 2 ,...,a n are positive integers,
1 1 1 1
+ + ··· + + then gcd(a 1 ,a 2 , ..., a n−1 ,a n ) = gcd(a 1 ,a 2 , ...,
1 · 2 2 · 3 (n − 1)n n(n + 1) a n−2 , gcd(a n−1 ,a n )).
3 1 1 1 b) Use part (a), together with the Euclidean algorithm, to
= − + − develop a recursive algorithm for computing the great-
2 n n n + 1
est common divisor of a set of n positive integers.
3 1
= − . ∗ 54. Describe a recursive algorithm for writing the greatest
2 n + 1
common divisor of n positive integers as a linear combi-
Hence, the result is true for n + 1 if it is true for n. This
nation of these integers.
completes the proof.
55. Find an explicit formula for f (n) if f(1) = 1 and f (n) =
48. Suppose that A 1 , A 2 ,...,A n are a collection of sets.
f(n − 1) + 2n − 1 for n ≥ 2. Prove your result using
Suppose that R 2 = A 1 ⊕ A 2 and R k = R k−1 ⊕ A k for mathematical induction.
k = 3, 4,...,n.Usemathematicalinductiontoprovethat
∗∗ 56. Give a recursive definition of the set of bit strings that
x ∈ R n if and only if x belongs to an odd number of the
sets A 1 ,A 2 ,...,A n . (Recall that S ⊕ T is the symmetric contain twice as many 0s as 1s.
difference of the sets S and T defined in the preamble to 57. Let S be the set of bit strings defined recursively by λ ∈ S
Exercise 32 of Section 2.2.) and 0x ∈ S, x1 ∈ S if x ∈ S, where λ is the empty string.
2
∗ 49. Show that n circles divide the plane into n − n + 2 re- a) Find all strings in S of length not exceeding five.
gions if every two circles intersect in exactly two points b) Give an explicit description of the elements of S.
and no three circles contain a common point. 58. Let S be the set of strings defined recursively by abc ∈ S,
∗ 50. Show that n planes divide three-dimensional space into bac ∈ S, and acb ∈ S, where a, b, and c are fixed letters;
3
(n + 5n + 6)/6 regions if any three of these planes have and for all x ∈ S, abcx ∈ S; abxc ∈ S, axbc ∈ S, and
exactly one point in common and no four contain a com- xabc ∈ S, where x is a variable representing a string of
mon point. letters.
√
∗ 51. Use the well-ordering property to show that 2isir- a) Find all elements of S of length eight or less.
√
rational. [Hint: Assume that 2 is rational. Show that b) Show that every element of S has a length divisible by
√
the set of positive integers of the form b 2 has a least three.
JOHN MCCARTHY (BORN 1927) John McCarthy was born in Boston. He grew up in Boston and in Los
Angeles.Hestudiedmathematicsasbothanundergraduateandagraduatestudent,receivinghisB.S.in1948from
the California Institute of Technology and his Ph.D. in 1951 from Princeton. After graduating from Princeton,
McCarthy held positions at Princeton, Stanford, Dartmouth, and M.I.T. He held a position at Stanford from 1962
until 1994, and is now an emeritus professor there. At Stanford, he was the director of the Artificial Intelligence
Laboratory, held a named chair in the School of Engineering, and was a senior fellow in the Hoover Institution.
McCarthy was a pioneer in the study of artificial intelligence, a term he coined in 1955. He worked
on problems related to the reasoning and information needs required for intelligent computer behavior. Mc-
Carthy was among the first computer scientists to design time-sharing computer systems. He developed LISP,
a programming language for computing using symbolic expressions. He played an important role in using logic to verify the correctness
of computer programs. McCarthy has also worked on the social implications of computer technology. He is currently working on
the problem of how people and computers make conjectures through assumptions that complications are absent from situations.
McCarthy is an advocate of the sustainability of human progress and is an optimist about the future of humanity. He has also begun
writing science fiction stories. Some of his recent writing explores the possibility that the world is a computer program written by
some higher force.
Among the awards McCarthy has won are the Turing Award from the Association for Computing Machinery, the Research
Excellence Award of the International Conference on Artificial Intelligence, the Kyoto Prize, and the National Medal of Science.