Page 363 - Discrete Mathematics and Its Applications
P. 363
342 5 / Induction and Recursion
parts of this exercise outline a strong induction proof that 12. Use strong induction to show that every positive integer n
P(n) is true for n ≥ 18. can be written as a sum of distinct powers of two, that is,
2
0
1
a) Show statements P(18), P(19), P(20), and P(21) as a sum of a subset of the integers 2 = 1, 2 = 2, 2 = 4,
are true, completing the basis step of the proof. and so on. [Hint: For the inductive step, separately con-
sider the case where k + 1 is even and where it is odd.
b) What is the inductive hypothesis of the proof?
When it is even, note that (k + 1)/2 is an integer.]
c) What do you need to prove in the inductive step?
∗ 13. A jigsaw puzzle is put together by successively joining
d) Complete the inductive step for k ≥ 21.
pieces that fit together into blocks. A move is made each
e) Explain why these steps show that this statement is time a piece is added to a block, or when two blocks
true whenever n ≥ 18. are joined. Use strong induction to prove that no matter
5. a) Determine which amounts of postage can be formed how the moves are carried out, exactly n − 1 moves are
using just 4-cent and 11-cent stamps. required to assemble a puzzle with n pieces.
b) Prove your answer to (a) using the principle of math- 14. Suppose you begin with a pile of n stones and split this
ematical induction. Be sure to state explicitly your pile into n piles of one stone each by successively split-
inductive hypothesis in the inductive step. ting a pile of stones into two smaller piles. Each time you
c) Prove your answer to (a) using strong induction. How split a pile you multiply the number of stones in each
does the inductive hypothesis in this proof differ from of the two smaller piles you form, so that if these piles
have r and s stones in them, respectively, you compute
that in the inductive hypothesis for a proof using math-
rs. Show that no matter how you split the piles, the sum
ematical induction?
of the products computed at each step equals n(n − 1)/2.
6. a) Determine which amounts of postage can be formed
using just 3-cent and 10-cent stamps. 15. Prove that the first player has a winning strategy for the
game of Chomp, introduced in Example 12 in Section 1.8,
b) Prove your answer to (a) using the principle of math-
if the initial board is square. [Hint: Use strong induction
ematical induction. Be sure to state explicitly your
to show that this strategy works. For the first move, the
inductive hypothesis in the inductive step.
first player chomps all cookies except those in the left and
c) Prove your answer to (a) using strong induction. How top edges. On subsequent moves, after the second player
does the inductive hypothesis in this proof differ from has chomped cookies on either the top or left edge, the
that in the inductive hypothesis for a proof using math- first player chomps cookies in the same relative positions
ematical induction? in the left or top edge, respectively.]
7. Which amounts of money can be formed using just two- ∗ 16. Prove that the first player has a winning strategy for the
dollar bills and five-dollar bills? Prove your answer using game of Chomp, introduced in Example 12 in Section 1.8,
strong induction. if the initial board is two squares wide, that is, a 2 × n
board. [Hint: Use strong induction. The first move of the
8. Suppose that a store offers gift certificates in denomina- first player should be to chomp the cookie in the bottom
tions of 25 dollars and 40 dollars. Determine the possible row at the far right.]
total amounts you can form using these gift certificates.
Prove your answer using strong induction. 17. Use strong induction to show that if a simple polygon
√ with at least four sides is triangulated, then at least two
∗ 9. Use strong induction to prove that 2 is irrational. [Hint:
√ of the triangles in the triangulation have two sides that
Let P(n) be the statement that 2 = n/b for any positive
border the exterior of the polygon.
integer b.]
∗ 18. Use strong induction to show that when a simple poly-
10. Assume that a chocolate bar consists of n squares ar- gon P with consecutive vertices v 1 , v 2 , ..., v n is trian-
ranged in a rectangular pattern. The entire bar, a smaller gulated into n − 2 triangles, the n − 2 triangles can be
rectangular piece of the bar, can be broken along a vertical numbered 1, 2,...,n − 2 so that v i is a vertex of triangle
or a horizontal line separating the squares.Assuming that i for i = 1, 2,...,n − 2.
only one piece can be broken at a time, determine how ∗ 19. Pick’s theorem says that the area of a simple poly-
many breaks you must successively make to break the bar gon P in the plane with vertices that are all lattice
into n separate squares. Use strong induction to prove points (that is, points with integer coordinates) equals
your answer.
I(P) +B(P)/2 − 1, where I(P) and B(P) are the
11. Consider this variation of the game of Nim. The game number of lattice points in the interior of P and on the
begins with n matches. Two players take turns removing boundary of P, respectively. Use strong induction on the
matches, one, two, or three at a time. The player remov- number of vertices of P to prove Pick’s theorem. [Hint:
ing the last match loses. Use strong induction to show For the basis step, first prove the theorem for rectangles,
that if each player plays the best strategy possible, the then for right triangles, and finally for all triangles by
first player wins if n = 4j,4j + 2, or 4j + 3 for some noting that the area of a triangle is the area of a larger
nonnegative integer j and the second player wins in the rectangle containing it with the areas of at most three tri-
remaining case when n = 4j + 1 for some nonnegative angles subtracted. For the inductive step, take advantage
integer j. of Lemma 1.]