Câu hỏi 120
Cho $k$ là số nguyên không âm. Có một đống gồm $2^{2^k}$ đồng xu, trong đó đúng một đồng là xu giả. Ta có vô hạn chó nghiệp vụ, trong đó có đúng một con bị ốm nhưng ta không biết là con nào. Một lần kiểm tra các đồng xu gồm ba bước: chọn ra một số đồng xu trong tất cả các đồng xu; chọn một con chó nghiệp vụ; cho con chó này ngửi đồng thời các đồng xu đã chọn. Nếu trong các đồng xu được chọn có xu giả thì con chó khỏe mạnh sau khi ngửi chắc chắn sẽ sủa; ngược lại thì chắc chắn không sủa. Còn con chó bị ốm thì sủa hay không sủa là ngẫu nhiên. Hãy thiết kế một quy trình sử dụng nhiều nhất $2^k + k + 2$ lần kiểm tra để tìm ra đồng xu giả, và chứng minh rằng quy trình đó thực hiện được.