Câu hỏi 96
Cho số nguyên dương $d \ge 3$. Các xâu nhị phân độ dài $d$ được chia thành $2^{d-1}$ cặp sao cho hai xâu trong mỗi cặp khác nhau ở đúng một vị trí. Chứng minh rằng tồn tại một chu trình xen kẽ có độ dài không quá $2d-2$, tức là có không quá $2d-2$ xâu nhị phân có thể xếp trên một vòng tròn sao cho hai xâu kề nhau bất kì khác nhau ở đúng một vị trí và đúng một nửa số cặp xâu kề nhau là các cặp trong cách chia.
(Lyuben Lichev)
(Lyuben Lichev)