Chapter 5: Q32E (page 359)
(a) Give a recursive definition of the function ones (s) , which counts the number of ones in a bit string s.
(b) Use structural induction to prove that ones (st) = ones (s) + ones (t) .
Over 30 million students worldwide already upgrade their learning with Vaia!
All the tools & learning materials you need for study success - in one app.
Get started for free
Suppose you begin with a pile of n stones and split this pile into n piles of one stone each by successively splitting a pile of stones into two smaller piles. Each time you split a pile of stones into two smaller piles. Each time you split a pile you multiply the number of stones in each of the two smaller piles you form, so that if piles haver and s stones in them, respectively, you compute rs. Show that no matter how you split the piles, the sum of the products computed at each step equals .
Give a recursive algorithm for finding whenever n! and m are positive integers.
Trace Algorithm 3 when it finds gcd (8,13). That is, show all the steps used by Algorithm 3 to find (8,13).
Consider this variation of the game of Nim. The game begins with n matches. Two players take turns removing matches, one, two, or three at a time. The player removing the last match loses. Using strong induction to show that if each player plays the best strategy possible, the first player wins if or for some nonnegative integer jand the second player wins in the remaining case when for some nonnegative integer j.
A jigsaw puzzle is put together by successively joining pieces that fit together into blocks. A move is made each time a piece is added to a block, or when two blocks are joined. Use strong induction to prove that no matter how the moves are carries out, exactlyn -1 moves are required to assemble a puzzle with n pieces.
What do you think about this solution?
We value your feedback to improve our textbook solutions.
