1996 USAMO Problems/Problem 4
Problem
An -term sequence in which each term is either 0 or 1 is called a binary sequence of length . Let be the number of binary sequences of length n containing no three consecutive terms equal to 0, 1, 0 in that order. Let be the number of binary sequences of length that contain no four consecutive terms equal to 0, 0, 1, 1 or 1, 1, 0, 0 in that order. Prove that for all positive integers .
(proposed by Kiran Kedlaya)
Solution
Given any binary sequence , define . The operator basically takes pairs of consecutive terms and returns 0 if the terms are the same and 1 otherwise. Note that for every sequence of length there exist exactly two binary sequences of length such that .
If does not contain the string 0, 1, 0, cannot contain either of the strings 0, 0, 1, 1 or 1, 1, 0, 0. Conversely, if does not contain the sequences 0, 0, 1, 1 or 1, 1, 0, 0, cannot contain 0, 1, 0. There are such and such . Since each corresponds with two , there are twice as many such as such ; thus, .
See Also
1996 USAMO (Problems • Resources) | ||
Preceded by Problem 3 |
Followed by Problem 5 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.