Consider the following problem. You are given a bit string of n bits. You can examine any bit in the string, to see if it contains 0 or 1. More precisely, the function probem.
(i) returns the value of the ith bit in the string (either 0 or 1). You wish to determine whether the bit string contains two consecutive 1 bits. Obviously, you can do this using n probes. For which values of n in the range {3, 4, 5, 6, 7} can this be done using fewer than n probes? Explain your answer carefully. Work out the answer for each of the ?ve values separately. The answers for smaller values of n may be helpful for ?nding the answers for larger values of n. "