# 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 22: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, .