Câu hỏi 95
Trưởng đoàn IMO của Brazil chọn hai số tự nhiên $n$ và $k$ với $n\gt k$, rồi cho phó đoàn và một thí sinh biết hai số này. Sau đó trưởng đoàn thì thầm vào tai phó đoàn một dãy nhị phân độ dài $n$. Phó đoàn viết ra tất cả các dãy nhị phân độ dài $n$ khác với dãy của trưởng đoàn ở đúng $k$ vị trí. (Ví dụ với $n=3$ và $k=1$: nếu trưởng đoàn chọn 101 thì phó đoàn viết ra 001, 100, 111.) Thí sinh nhìn vào các dãy mà phó đoàn đã viết ra. Bây giờ thí sinh cố gắng tìm ra dãy ban đầu của trưởng đoàn.
Thí sinh cần đoán ít nhất bao nhiêu lần (phụ thuộc vào $n$ và $k$) để chắc chắn có một lần đoán đúng?
Thí sinh cần đoán ít nhất bao nhiêu lần (phụ thuộc vào $n$ và $k$) để chắc chắn có một lần đoán đúng?