Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(added solution)
 
(→‎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 $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$.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1996_USAMO_Problems/Problem_4&oldid=71359"