Difference between revisions of "1996 USAMO Problems/Problem 4"

m
m (See Also)
 
Line 12: Line 12:
  
 
== See Also ==
 
== See Also ==
{{USAMO box|year=1996|num-b=3|num-a=5}}
+
{{USAMO newbox|year=1996|num-b=3|num-a=5}}
 
{{MAA Notice}}
 
{{MAA Notice}}
 
[[Category:Olympiad Combinatorics Problems]]
 
[[Category:Olympiad Combinatorics Problems]]

Latest revision as of 09:28, 20 July 2016

Problem

An $n$-term sequence $(x_1, x_2, \ldots, x_n)$ in which each term is either 0 or 1 is called a binary sequence of length $n$. Let $a_n$ be the number of binary sequences of length n containing no three consecutive terms equal to 0, 1, 0 in that order. Let $b_n$ be the number of binary sequences of length $n$ that contain no four consecutive terms equal to 0, 0, 1, 1 or 1, 1, 0, 0 in that order. Prove that $b_{n+1} = 2a_n$ for all positive integers $n$.

(proposed by Kiran Kedlaya)

Solution

Given any binary sequence $B=(b_1,b_2,b_3,\dots,b_k)$, define $f(B)=(|b_2-b_1|,|b_3-b_2|,\dots,|b_k-b_{k-1}|)$. The operator $f$ basically takes pairs of consecutive terms and returns 0 if the terms are the same and 1 otherwise. Note that for every sequence $S$ of length $n$ there exist exactly two binary sequences $B$ of length $n+1$ such that $f(B)=S$.

If $f(B)$ does not contain the string 0, 1, 0, $B$ cannot contain either of the strings 0, 0, 1, 1 or 1, 1, 0, 0. Conversely, if $B$ does not contain the sequences 0, 0, 1, 1 or 1, 1, 0, 0, $f(B)$ cannot contain 0, 1, 0. There are $a_n$ such $f(B)$ and $b_{n+1}$ such $B$. Since each $S$ corresponds with two $B$, there are twice as many such $B$ as such $S$; thus, $b_{n+1}=2a_n$.

See Also

1996 USAMO (ProblemsResources)
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. AMC logo.png