Page 352 - Discrete Mathematics and Its Applications

5.1 Mathematical Induction 331

39. Prove that if A 1 ,A 2 ,...,A n and B 1 ,B 2 ,...,B n are sets Inductive Step: Assume that P(k) is true, so that all
such that A j ⊆ B j for j = 1, 2,...,n, then the horses in any set of k horses are the same color.
Consider any k + 1 horses; number these as horses
n n
1, 2, 3,...,k,k + 1. Now the first k of these horses all

A j ⊆ B j .
must have the same color, and the last k of these must
j = 1 j = 1
also have the same color. Because the set of the first k
40. Prove that if A 1 , A 2 ,...,A n and B are sets, then
horses and the set of the last k horses overlap, all k + 1
(A 1 ∩ A 2 ∩ ··· ∩ A n ) ∪ B must be the same color. This shows that P(k + 1) is true
= (A 1 ∪ B) ∩ (A 2 ∪ B) ∩ ··· ∩ (A n ∪ B). and finishes the proof by induction.
50. What is wrong with this “proof”?
41. Prove that if A 1 , A 2 ,...,A n and B are sets, then n
“Theorem” For every positive integer n, i = 1 i =
1 2
(A 1 ∪ A 2 ∪ ··· ∪ A n ) ∩ B (n + ) /2.
2
= (A 1 ∩ B) ∪ (A 2 ∩ B) ∪ ··· ∪ (A n ∩ B).
Basis Step: The formula is true for n = 1.
42. Prove that if A 1 , A 2 ,...,A n and B are sets, then n 1 2
Inductive Step: Suppose that i = (n + ) /2.
i=1 2
(A 1 − B) ∩ (A 2 − B) ∩ ··· ∩ (A n − B) Then n+1 i = ( n i=1 i) + (n + 1). By the induc-
i=1
= (A 1 ∩ A 2 ∩ ··· ∩ A n ) − B. n+1 1 2
tive hypothesis, i=1 i = (n + ) /2 + n + 1 =
2
2 1 2 9
43. Prove that if A 1 , A 2 ,...,A n are subsets of a universal (n + n + )/2 + n + 1 = (n + 3n + 4 )/2 =
4
1 2
3 2
set U, then (n + ) /2 =[(n + 1) + ] /2, completing the induc-
2 2
tive step.
n

n 51. What is wrong with this “proof”?
A k = k = 1 A k .
k = 1 “Theorem” For every positive integer n,if x and y are
positive integers with max(x, y) = n, then x = y.
44. Prove that if A 1 ,A 2 ,...,A n and B are sets, then
Basis Step: Suppose that n = 1. If max(x, y) = 1 and x
(A 1 − B) ∪ (A 2 − B) ∪ ··· ∪ (A n − B) and y are positive integers, we have x = 1 and y = 1.
= (A 1 ∪ A 2 ∪ ··· ∪ A n ) − B.
Inductive Step: Let k be a positive integer. Assume that
45. Prove that a set with n elements has n(n − 1)/2 subsets whenever max(x, y) = k and x and y are positive inte-
containing exactly two elements whenever n is an integer gers, then x = y. Now let max(x, y) = k + 1, where x
greater than or equal to 2. and y are positive integers. Then max(x − 1,y − 1) = k,
so by the inductive hypothesis, x − 1 = y − 1. It follows
∗ 46. Prove that a set with n elements has n(n − 1)(n − 2)/6
subsets containing exactly three elements whenever n is that x = y, completing the inductive step.
an integer greater than or equal to 3. 52. Suppose that m and n are positive integers with m>n
and f is a function from {1, 2,...,m} to {1, 2,...,n}.
In Exercises 47 and 48 we consider the problem of placing
towers along a straight road, so that every building on the Use mathematical induction on the variable n to show
road receives cellular service.Assume that a building receives that f is not one-to-one.
∗ 53. Use mathematical induction to show that n people can di-
cellular service if it is within one mile of a tower.
vide a cake (where each person gets one or more separate
47. Devise a greedy algorithm that uses the minimum number pieces of the cake) so that the cake is divided fairly, that
of towers possible to provide cell service to d buildings is, in the sense that each person thinks he or she got at
located at positions x 1 ,x 2 ,...,x d from the start of the least (1/n)th of the cake. [Hint: For the inductive step,
road. [Hint: At each step, go as far as possible along the take a fair division of the cake among the first k people,
road before adding a tower so as not to leave any buildings have each person divide their share into what this per-
without coverage.]
son thinks are k + 1 equal portions, and then have the
∗ 48. Use mathematical induction to prove that the algorithm (k + 1)st person select a portion from each of the k peo-
you devised in Exercise 47 produces an optimal solution, ple. When showing this produces a fair division for k + 1
that is, that it uses the fewest towers possible to provide people, suppose that person k + 1 thinks that person i got
cellular service to all buildings. p i of the cake where k i=1 p i = 1.]
Exercises 49–51 present incorrect proofs using mathemati- 54. Use mathematical induction to show that given a set of
cal induction. You will need to identify an error in reasoning n + 1 positive integers, none exceeding 2n, there is at
in each exercise. least one integer in this set that divides another integer in
49. What is wrong with this “proof” that all horses are the the set.
same color? ∗ 55. A knight on a chessboard can move one space horizon-
Let P(n) be the proposition that all the horses in a set tally (in either direction) and two spaces vertically (in
of n horses are the same color. either direction) or two spaces horizontally (in either di-
rection) and one space vertically (in either direction).
Basis Step: Clearly, P(1) is true. Suppose that we have an infinite chessboard, made up