Difference between revisions of "1996 USAMO Problems/Problem 4"
(added solution) |
AllenWang314 (talk | contribs) (→Problem) |
||
Line 2: | Line 2: | ||
An <math>n</math>-term sequence <math>(x_1, x_2, \ldots, x_n)</math> in which each term is either 0 or 1 is called a binary sequence of length <math>n</math>. Let <math>a_n</math> be the number of binary sequences of length n containing no three consecutive terms equal to 0, 1, 0 in that order. Let <math>b_n</math> be the number of binary sequences of length <math>n</math> that contain no four consecutive terms equal to 0, 0, 1, 1 or 1, 1, 0, 0 in that order. Prove that <math>b_{n+1} = 2a_n</math> for all positive integers <math>n</math>. | An <math>n</math>-term sequence <math>(x_1, x_2, \ldots, x_n)</math> in which each term is either 0 or 1 is called a binary sequence of length <math>n</math>. Let <math>a_n</math> be the number of binary sequences of length n containing no three consecutive terms equal to 0, 1, 0 in that order. Let <math>b_n</math> be the number of binary sequences of length <math>n</math> that contain no four consecutive terms equal to 0, 0, 1, 1 or 1, 1, 0, 0 in that order. Prove that <math>b_{n+1} = 2a_n</math> for all positive integers <math>n</math>. | ||
+ | |||
+ | (proposed by Kiran Kedlaya) | ||
==Solution== | ==Solution== |
Revision as of 21:16, 26 July 2015
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,
.