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 "2001 IMO Shortlist Problems/C6"

(New page: == Problem == For a positive integer <math>n</math> define a sequence of zeros and ones to be [i]balanced[/i] if it contains <math>n</math> zeros and <math>n</math> ones. Two balanced sequ...)
 
m (corrected consequences of mindless copying and pasting :P)
 
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
For a positive integer <math>n</math> define a sequence of zeros and ones to be [i]balanced[/i] if it contains <math>n</math> zeros and <math>n</math> ones. Two balanced sequences <math>a</math> and <math>b</math> are [i]neighbors[/i] if you can move one of the <math>2n</math> symbols of <math>a</math> to another position to form <math>b</math>. For instance, when <math>n = 4</math>, the balanced sequences <math>01101001</math> and <math>00110101</math> are neighbors because the third (or fourth) zero in the first sequence can be moved to the first or second position to form the second sequence. Prove that there is a set <math>S</math> of at most <math>\frac {1}{n + 1} \binom{2n}{n}</math> balanced sequences such that every balanced sequence is equal to or is a neighbor of at least one sequence in <math>S</math>.
+
For a positive integer <math>n</math> define a sequence of zeros and ones to be <i>balanced</i> if it contains <math>n</math> zeros and <math>n</math> ones. Two balanced sequences <math>a</math> and <math>b</math> are <i>neighbors</i> if you can move one of the <math>2n</math> symbols of <math>a</math> to another position to form <math>b</math>. For instance, when <math>n = 4</math>, the balanced sequences <math>01101001</math> and <math>00110101</math> are neighbors because the third (or fourth) zero in the first sequence can be moved to the first or second position to form the second sequence. Prove that there is a set <math>S</math> of at most <math>\frac {1}{n + 1} \binom{2n}{n}</math> balanced sequences such that every balanced sequence is equal to or is a neighbor of at least one sequence in <math>S</math>.
  
 
== Solution ==
 
== Solution ==

Latest revision as of 17:34, 20 August 2008

Problem

For a positive integer $n$ define a sequence of zeros and ones to be balanced if it contains $n$ zeros and $n$ ones. Two balanced sequences $a$ and $b$ are neighbors if you can move one of the $2n$ symbols of $a$ to another position to form $b$. For instance, when $n = 4$, the balanced sequences $01101001$ and $00110101$ are neighbors because the third (or fourth) zero in the first sequence can be moved to the first or second position to form the second sequence. Prove that there is a set $S$ of at most $\frac {1}{n + 1} \binom{2n}{n}$ balanced sequences such that every balanced sequence is equal to or is a neighbor of at least one sequence in $S$.

Solution

This problem needs a solution. If you have a solution for it, please help us out by adding it.

Resources

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2001_IMO_Shortlist_Problems/C6&oldid=27507"