1996 USAMO Problems/Problem 4

Revision as of 21:16, 26 July 2015 by AllenWang314 (talk | contribs) (Problem)

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$.