rafaello wrote: We are given a collection of $2^{2^k}$ coins, where $k$ is a non-negative integer. Exactly one coin is fake. We have an unlimited number of service dogs. One dog is sick but we do not know which one. A test consists of three steps: select some coins from the collection of all coins; choose a service dog; the dog smells all of the selected coins at once. A healthy dog will bark if and only if the fake coin is amongst them. Whether the sick dog will bark or not is random. Devise a strategy to find the fake coin, using at most $2^k+k+2$ tests, and prove that it works. For obvious reasons it is pointless to ask the same dog to smell twice, since then we have a huge chance of losing. And now the problem has appeared in Pascal96's combinatorics book, which can be found here. (see Pg 44, example 10 (b))

This is a really beautiful problem! Label the coins from $0$ to $2^{2^k}-1$ and assign to each coin a $2^k$-digit binary, according to its label's base two representation. Now, choose $2^k$ random dogs and for each $1\leqslant i\leqslant 2^k$, give to the $i^{\text{th}}$ dog the set of coins which have $0$ on the $i^{\text{th}}$ position in the assigned binary. After the $2^k$ queries are performed, we get a piece of information about each digit of the binary of the fake coin (if the dog barks, the fake coin must have a $0$ on the $i^{\text{th}}$ position, and a $1$ otherwise). Out of these pieces of information, at most one is wrong, in the case that the sick dog was among the $2^k$ selected ones, and responded falsely. Let the binary we got from the first $2^k$ queries be $B$. Choose two more dogs, different from the initial $2^k$ ones, and ask them both whether the coin corresponding to this binary is the fake one. The (first) crucial observation is that among these two dogs, at least one is healthy. We now have two cases; firstly, if the two dogs answer differently, then clearly the sick dog is among them. Consequently, the initial $2^k$ dogs were all healthy and, indeed, $B$ is the binary corresponding to the fake coin. Secondly, if both dogs give the same answer, then whatever that answer is, it is the truth. If the answer is affirmative, then $B$ is the binary corresponding to the fake coin, and we finish. If the answer is negative, the (second) crucial observation is that the sick dog must have been among the initial $2^k$ ones, so the two dogs we have just asked are healthy! Therefore, we may pick any of them and perform a (truthful) binary search on the bits of $B$, in order to find the switched one and deduce the binary corresponding to the fake coin. Note that this binary search uses $k$ queries. Therefore, using a total of at most $2^k+k+2$ queries, we can indeed find the fake coin.