Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
A sensor sends signals as strings of the digits and . To avoid a fault, the first design never sends two s next to each other. A second design allows two s next to each other but never three in a row.
Count the strings of length allowed by the first design. Then count the strings of length allowed by the second design. For each design set up a recurrence by looking at how a string ends: after its last , how many s can follow? Give the starting values you use.
Name the count . Split on the first or the last step so that each case is a smaller copy of the same question. Check that the cases do not overlap and cover everything, then find the starting values by hand.
Check an answer or open a hint to unlock the worked solution.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Plan. Split each string on its ending, then work forward.
Step 1. First design. A good string of length ends in (after a good string of length ) or in (after a good string of length ). So with and .
Step 2. Work forward. 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, so .
Step 3. Second design. A good string ends in , or , after a good string of length , or . So . Use (the empty string), and .
Step 4. Work forward. , , , , , .
Check. Of the strings of length only is banned in the second design, which gives .
Answer: strings for the first design and for the second.
Log in to join the discussion.
Loading…