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.]
   358   359   360   361   362   363   364   365   366   367   368