Difference between revisions of "1996 USAMO Problems/Problem 4"
AllenWang314 (talk | contribs) (→Problem) |
m |
||
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 box|year=1996|num-b=3|num-a=5}} | ||
+ | {{MAA Notice}} | ||
+ | [[Category:Olympiad Combinatorics Problems]] |
Revision as of 09:26, 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 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.