Câu hỏi 106
Trưởng đoàn của một đội tuyển IMO chọn các số nguyên dương $n$ và $k$ với $n \gt k$, rồi thông báo chúng cho phó đoàn và một thí sinh. Sau đó trưởng đoàn bí mật cho phó đoàn biết một xâu nhị phân gồm $n$ chữ số, và phó đoàn viết ra tất cả các xâu nhị phân gồm $n$ chữ số khác với xâu của trưởng đoàn ở đúng $k$ vị trí. (Ví dụ, nếu $n = 3$ và $k = 1$, và trưởng đoàn chọn 101, thì phó đoàn sẽ viết ra 001, 111 và 100.) Thí sinh, người được phép xem các xâu do phó đoàn viết, cố gắng đoán xâu của trưởng đoàn. Cần tối thiểu bao nhiêu lần đoán (theo $n$ và $k$) để đảm bảo có câu trả lời đúng?