Q8 Matemática  (Baltic Way 2021)

Recebemos uma coleção de moedas de $2^{2^k}$, onde $k$ é um inteiro não negativo. Exatamente uma moeda é falsa. Temos um número ilimitado de cães de serviço. Um cão está doente, mas não sabemos qual. Um teste consiste em três etapas: selecionar algumas moedas da coleção de todas as moedas; escolha um cão de serviço; o cachorro cheira todas as moedas selecionadas de uma só vez. Um cão saudável vai latir se e somente se a moeda falsa estiver entre eles. Se o cão doente vai latir ou não é aleatório. Elabore uma estratégia para encontrar a moeda falsa, usando no máximo testes $2^k+k+2$, e prove que funciona.