IMO 2001 SL C6

Origin: CAN | Category: Combinatorics

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 n+1
2n n  balanced sequences such that every balanced sequence is equal to or is a neighbor of at least one sequence in S.

Solution

For each balanced sequence a = (a1, a2, . . . , a2n) denote by f(a) the sum of j’s for which aj = 1 (for example, f(100101) = 1 + 4 + 6 = 11). Partition the
2n n  balanced sequences into n + 1 classes according to the residue of f modulo n + 1. Now take S to be a class of minimum size: obviously |S| \leq n+1
2n n  . We claim that every balanced sequence a is either a member of S or a neighbor of a member of S. We consider two cases. (i) Let a1 be 1. It is easy to see that moving this 1 just to the right of the kth 0, we obtain a neighboring balanced sequence b with f(b) = f(a) + k. Thus if a ̸\inS, taking a suitable k \in{1, 2, . . ., n} we can achieve that b \inS. (ii) Let a1 be 0. Taking this 0 just to the right of the kth 1 gives a neighbor b with f(b) = f(a) −k, and the conclusion is similar to that of (i). This justifies our claim.