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)
 
m (→‎See Also)
 
(2 intermediate revisions by 2 users not shown)
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==
Line 8: Line 10:
  
 
If <math>f(B)</math> does not contain the string 0, 1, 0, <math>B</math> cannot contain either of the strings 0, 0, 1, 1 or 1, 1, 0, 0. Conversely, if <math>B</math> does not contain the sequences 0, 0, 1, 1 or 1, 1, 0, 0, <math>f(B)</math> cannot contain 0, 1, 0. There are <math>a_n</math> such <math>f(B)</math> and <math>b_{n+1}</math> such <math>B</math>. Since each <math>S</math> corresponds with two <math>B</math>, there are twice as many such <math>B</math> as such <math>S</math>; thus, <math>b_{n+1}=2a_n</math>.
 
If <math>f(B)</math> does not contain the string 0, 1, 0, <math>B</math> cannot contain either of the strings 0, 0, 1, 1 or 1, 1, 0, 0. Conversely, if <math>B</math> does not contain the sequences 0, 0, 1, 1 or 1, 1, 0, 0, <math>f(B)</math> cannot contain 0, 1, 0. There are <math>a_n</math> such <math>f(B)</math> and <math>b_{n+1}</math> such <math>B</math>. Since each <math>S</math> corresponds with two <math>B</math>, there are twice as many such <math>B</math> as such <math>S</math>; thus, <math>b_{n+1}=2a_n</math>.
 +
 +
== See Also ==
 +
{{USAMO newbox|year=1996|num-b=3|num-a=5}}
 +
{{MAA Notice}}
 +
[[Category:Olympiad Combinatorics Problems]]

Latest revision as of 08: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 (Problems • Resources)
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

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