Câu hỏi 9
Trưởng đoàn IMO chọn các số nguyên dương $n$, $k$ với $n\gt k$, rồi thông báo cho phó đoàn và một thí sinh. Trưởng đoàn bí mật cho phó đoàn biết một chuỗi nhị phân dài $n$ chữ số; phó đoàn viết tất cả chuỗi dài $n$ chữ số khác chuỗi ấy ở đúng $k$ vị trí. Ví dụ, với $n=3$, $k=1$, chuỗi trưởng đoàn chọn là 101 thì phó đoàn viết 001, 111, 100. Thí sinh được xem các chuỗi phó đoàn viết và đoán chuỗi trưởng đoàn. Tìm số lần đoán ít nhất, theo $n$, $k$, để chắc chắn đoán đúng.