Câu hỏi 12
Với một số nguyên dương n, gọi một dãy các ký hiệu 0 và 1 là cân bằng nếu nó chứa n ký hiệu 0 và n ký hiệu 1. Hai dãy cân bằng a và b được gọi là láng giềng nếu có thể chuyển một trong 2n ký hiệu của a sang một vị trí khác để được b. Chẳng hạn, khi n = 4, hai dãy cân bằng 01101001 và 00110101 là láng giềng: có thể chuyển ký hiệu 0 thứ ba (hoặc thứ tư) của dãy thứ nhất đến vị trí thứ nhất hoặc thứ hai để được dãy thứ hai. Chứng minh rằng tồn tại một tập S gồm không quá $\frac{1}{n+1}\binom{2n}{n}$ dãy cân bằng sao cho mỗi dãy cân bằng hoặc thuộc S, hoặc là láng giềng của ít nhất một dãy trong S.