Math 471 Week 1 Case Study

Math 471
Problem 1.

Group Work #8

Fall 2011

(a): Find a recurrence relation for the number tn of bit strings of length n that contain three consecutive zeros. SOLUTION: We break up all of the bit strings of length n according to the following nonoverlapping cases: • Bit Strings Beginning with “1”: In this case, the three consecutive zeros must appear in the last n − 1 slots, and there are tn−1 bit strings that will have three consecutive zeros there. • Bit Strings Beginning with “01”: In this case, the three consecutive zeros must appear in the last n − 2 slots, and there are tn−2 bit strings that will have three consecutive zeros there. • Bit Strings Beginning with “001”: In this case, the three consecutive zeros must appear in the…show more content…
SOLUTION: We observe directly that t1 = t2 = 0 and t3 = 1. Now according to the relation in (a), t4 = 1 + 0 + 0 + 21 = 3. Likewise, t5 = 3 + 1 + 0 + 22 = 8, t6 = 8 + 3 + 1 + 23 = 20, and t7 = 20 + 8 + 3 + 24 = 47. So the answer is 47. Problem 2. Find a recurrence relation for un , the number of bit strings of length n that do not contain two consecutive zeros, by (a): using the recurrence relation zn for the number of bit strings of length n that do contain two consecutive zeros. SOLUTION: We simply observe that all strings of length n either do or don’t have two consecutive zeros; mathematically, this means that zn +un = 2n . Hence, un = 2n −zn = 2n −(zn−1 +zn−2 +2n−2 ). (b): by reasoning from scratch. SOLUTION: We break up bit strings of length n into two cases: • Bit strings beginning with 1: There are un−1 ways to finish such a string such that there are no two consecutive…show more content…
Adding the two cases above, we arrive at the answer: un = un−1 + un−2 . (c): Use either (a) or (b) to determine the number of bit strings of length 7 that do not contain two consecutive zeros. SOLUTION: We note directly that u1 = 2 and u2 = 3. Then u3 = 2 + 3 = 5, u4 = 3 + 5 = 8, u5 = 5 + 8 = 13, u6 = 8 + 13 = 21, and u7 = 13 + 21 = 34. Problem 3. A country uses as currency coins with values of 1 peso, 2 pesos, 5 pesos, 10 pesos and bills with values of 5 pesos, 10 pesos, 20 pesos, 50 pesos, and 100 pesos. Find a recurrence relation for the number of ways bn to pay a bill of n pesos (for n ≥ 101) if the order in which the coins and bills are paid matters. SOLUTION: We break bn up according to which coin or bill was used first. If we start with a 1 peso coin, then there are bn−1 ways to finish paying the bill. If we start with a 2 peso coin, then there are bn−2 ways to finish paying the bill. If we start with a 5 peso coin, then there are bn−5 ways to finish paying the bill. And so on. The final answer is bn = bn−1 + bn−2 + 2bn−5 + 2bn−10 + bn−20 + bn−50 + bn−100