« Vrati se
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.

Slični zadaci

#NaslovOznakeRj.KvalitetaTežina
2301IMO Shortlist 2009 problem C56
2186IMO Shortlist 2005 problem C55
2077IMO Shortlist 2001 problem C70
2075IMO Shortlist 2001 problem C56
2073IMO Shortlist 2001 problem C33
1862IMO Shortlist 1993 problem C50