1996 USAMO Problems/Problem 4: Difference between revisions
AllenWang314 (talk | contribs) |
|||
| (One intermediate revision by the same user not shown) | |||
| Line 10: | Line 10: | ||
If <math>f(B)</math> does not contain the string 0, 1, 0, <math>B</math> cannot contain either of the strings 0, 0, 1, 1 or 1, 1, 0, 0. Conversely, if <math>B</math> does not contain the sequences 0, 0, 1, 1 or 1, 1, 0, 0, <math>f(B)</math> cannot contain 0, 1, 0. There are <math>a_n</math> such <math>f(B)</math> and <math>b_{n+1}</math> such <math>B</math>. Since each <math>S</math> corresponds with two <math>B</math>, there are twice as many such <math>B</math> as such <math>S</math>; thus, <math>b_{n+1}=2a_n</math>. | If <math>f(B)</math> does not contain the string 0, 1, 0, <math>B</math> cannot contain either of the strings 0, 0, 1, 1 or 1, 1, 0, 0. Conversely, if <math>B</math> does not contain the sequences 0, 0, 1, 1 or 1, 1, 0, 0, <math>f(B)</math> cannot contain 0, 1, 0. There are <math>a_n</math> such <math>f(B)</math> and <math>b_{n+1}</math> such <math>B</math>. Since each <math>S</math> corresponds with two <math>B</math>, there are twice as many such <math>B</math> as such <math>S</math>; thus, <math>b_{n+1}=2a_n</math>. | ||
== See Also == | |||
{{USAMO newbox|year=1996|num-b=3|num-a=5}} | |||
{{MAA Notice}} | |||
[[Category:Olympiad Combinatorics Problems]] | |||
Latest revision as of 08:28, 20 July 2016
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 | ||
These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. Error creating thumbnail: File missing
