Câu hỏi 34
Trong một phép thử, một con chó nghiệp vụ ngửi một đống đồng xu và sủa nếu trong đó có đồng xu giả. Nếu chó bị bệnh thì việc nó sủa hay không là ngẫu nhiên, không phụ thuộc vào việc có đồng xu giả. Giả sử $k\le2^s$ và ta có $2^k$ đồng xu, trong đó đúng một đồng là giả. Có rất nhiều chó nghiệp vụ, đúng một con bị bệnh nhưng ta không biết con nào. Hãy xây dựng một chiến lược tìm đồng xu giả bằng nhiều nhất $k+s+2$ phép thử.