Solution
No Three Alike
Show the problem again
How many strings of length 12 over the alphabet {0, 1} contain neither 000 nor 111 as three consecutive characters? Give an integer.
Worked solution
**Answer: 466.** Break a string into maximal runs of equal symbols. The condition says every run has length 1 or 2. Conversely, a string is fixed by its first symbol together with its sequence of run lengths, since the runs must alternate symbols. So we need 2 times the number of ordered ways to write 12 as a sum of 1s and 2s. That number is the Fibonacci number F(13) = 233 (the same count as climbing 12 stairs in strides of 1 or 2). The answer is 2 × 233 = 466.
Source: Classic exercise in wide circulation; no traceable original source. Statement written for AxiomIQ.