Question 34
During one test a service dog smells a pile of coins and barks if there is a fake coin in it. If a dog is sick, whether it barks or not does not depend on the presence of fake coin, it happens randomly. Suppose $k \le 2^s$ and that we have $2^k$ coins, exactly one of which is fake. Assume that we have an excess number of service dogs, one of them is sick but we do not know which one. Device a strategy to find the fake coin using at most $k+s+2$ tests.