Câu hỏi 150
Cho $n, k$ là các số nguyên dương với $n \gt k$. Có hai người Giáp và Ất:
1. Giáp trước hết bí mật viết lên một mảnh giấy một dãy 0-1 có $n$ chữ số, và viết lên bảng tất cả các dãy 0-1 độ dài $n$ khác dãy này ở đúng $k$ vị trí. Ví dụ, nếu $n=3, k=1$ và dãy trên mảnh giấy là 101 thì Giáp phải viết lên bảng 001, 111 và 100.
2. Sau đó, Ất nhìn tất cả các dãy trên bảng và cố đoán dãy trên mảnh giấy. Mỗi lần anh ta được đoán một dãy 0-1 có $n$ chữ số, và Giáp phải trả lời trung thực là đoán đúng hay sai.
Với mỗi cặp $(n, k)$, tìm số nguyên dương $m$ nhỏ nhất sao cho Ất có một chiến lược đoán đảm bảo đoán đúng trong vòng $m$ lần.
1. Giáp trước hết bí mật viết lên một mảnh giấy một dãy 0-1 có $n$ chữ số, và viết lên bảng tất cả các dãy 0-1 độ dài $n$ khác dãy này ở đúng $k$ vị trí. Ví dụ, nếu $n=3, k=1$ và dãy trên mảnh giấy là 101 thì Giáp phải viết lên bảng 001, 111 và 100.
2. Sau đó, Ất nhìn tất cả các dãy trên bảng và cố đoán dãy trên mảnh giấy. Mỗi lần anh ta được đoán một dãy 0-1 có $n$ chữ số, và Giáp phải trả lời trung thực là đoán đúng hay sai.
Với mỗi cặp $(n, k)$, tìm số nguyên dương $m$ nhỏ nhất sao cho Ất có một chiến lược đoán đảm bảo đoán đúng trong vòng $m$ lần.