Page 353 - Discrete Mathematics and Its Applications

332 5 / Induction and Recursion

of all squares (m, n) where m and n are nonnegative inte- ∗ 66. Use the well-ordering property to show that the follow-
gers that denote the row number and the column number ing form of mathematical induction is a valid method to
of the square, respectively. Use mathematical induction to prove that P(n) is true for all positive integers n.
show that a knight starting at (0, 0) can visit every square
using a finite sequence of moves. [Hint: Use induction Basis Step: P(1) and P(2) are true.
on the variable s = m + n.] Inductive Step: For each positive integer k,if P(k) and
56. Suppose that P(k + 1) are both true, then P(k + 2) is true.

67. Show that if A 1 , A 2 ,...,A n are sets where n ≥ 2, and
a 0
A = , for all pairs of integers i and j with 1 ≤ i< j ≤ n either
0 b
A i is a subset of A j or A j is a subset of A i , then there is
where a and b are real numbers. Show that an integer i,1 ≤ i ≤ n such that A i is a subset of A j for

n all integers j with 1 ≤ j ≤ n.
a 0
n
A = n
0 b ∗ 68. A guest at a party is a celebrity if this person is known
by every other guest, but knows none of them. There is at
for every positive integer n.
most one celebrity at a party, for if there were two, they
57. (Requirescalculus) Usemathematicalinductiontoprove would know each other. A particular party may have no
n
that the derivative of f(x) = x equals nx n−1 whenever celebrity. Your assignment is to find the celebrity, if one
n is a positive integer. (For the inductive step, use the exists, at a party, by asking only one type of question—
product rule for derivatives.) asking a guest whether they know a second guest. Ev-
58. Suppose that A and B are square matrices with the prop- eryone must answer your questions truthfully. That is, if
n
n
erty AB = BA. Show that AB = B A for every positive Alice and Bob are two people at the party, you can askAl-
integer n. ice whether she knows Bob; she must answer correctly.
59. Suppose that m is a positive integer. Use mathematical Use mathematical induction to show that if there are n
induction to prove that if a and b are integers with a ≡ b people at the party, then you can find the celebrity, if
k
k
(mod m), then a ≡ b (mod m) whenever k is a nonneg- there is one, with 3(n − 1) questions. [Hint: First ask a
ative integer. question to eliminate one person as a celebrity. Then use
the inductive hypothesis to identify a potential celebrity.
60. Use mathematical induction to show that ¬(p 1 ∨ p 2 ∨
Finally, ask two more questions to determine whether that
··· ∨ p n ) is equivalent to ¬p 1 ∧¬p 2 ∧ · · ·∧¬p n
whenever p 1 , p 2 ,...,p n are propositions. person is actually a celebrity.]
Suppose there are n people in a group, each aware of a scandal
∗ 61. Show that
no one else in the group knows about. These people commu-
[(p 1 → p 2 ) ∧ (p 2 → p 3 ) ∧ ··· ∧ (p n−1 → p n )] nicate by telephone; when two people in the group talk, they
→[(p 1 ∧ p 2 ∧ ··· ∧ p n−1 ) → p n ]
share information about all scandals each knows about. For
is a tautology whenever p 1 ,p 2 ,...,p n are propositions, example, on the first call, two people share information, so
where n ≥ 2. by the end of the call, each of these people knows about two
2
∗ 62. Show that n lines separate the plane into (n + n + 2)/2 scandals. The gossip problem asks for G(n), the minimum
number of telephone calls that are needed for all n people to
regions if no two of these lines are parallel and no three
learn about all the scandals. Exercises 69–71 deal with the
pass through a common point.
gossip problem.
∗∗ 63. Let a 1 ,a 2 ,...,a n be positive real numbers. The arith-
metic mean of these numbers is defined by 69. Find G(1), G(2), G(3), and G(4).
70. Use mathematical induction to prove that G(n) ≤ 2n − 4
A = (a 1 + a 2 + ··· + a n )/n,
for n ≥ 4. [Hint: In the inductive step, have a new person
and the geometric mean of these numbers is defined by call a particular person at the start and at the end.]
G = (a 1 a 2 ··· a n ) 1/n . ∗∗ 71. Prove that G(n) = 2n − 4 for n ≥ 4.
∗ 72. Show that it is possible to arrange the numbers 1, 2,...,n
Use mathematical induction to prove that A ≥ G.
in a row so that the average of any two of these numbers
64. Use mathematical induction to prove Lemma 3 of never appears between them. [Hint: Show that it suffices
Section 4.3, which states that if p is a prime to prove this fact when n is a power of 2. Then use math-
and p | a 1 a 2 ··· a n , where a i is an integer for ematical induction to prove the result when n is a power
i = 1, 2, 3,...,n, then p | a i for some integer i.
of 2.]
65. Show that if n is a positive integer, then
∗ 73. Show that if I 1 ,I 2 ,...,I n is a collection of open in-
1 tervals on the real number line, n ≥ 2, and every pair
= n.
a 1 a 2 ··· a k of these intervals has a nonempty intersection, that is,
{a 1 ,...,a k }⊆{1,2,...,n}
I i ∩ I j =∅ whenever 1 ≤ i ≤ n and 1 ≤ j ≤ n, then
(Here the sum is over all nonempty subsets of the set of the intersection of all these sets is nonempty, that is,
the n smallest positive integers.) I 1 ∩ I 2 ∩ ··· ∩ I n =∅. (Recall that an open interval is