BALTIC-WAY 2021 Problem 8

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.