MathDB

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.

Problem Statement