We have a set of possible "key"s represented by bitstrings of length $k$. For example, when $k=3$, it can be $S = \{001, 010, 011, 000, 111\}$. I would like to find a "guess", which maximizes the Hamming distance of itself and the possible keys, assuming that the keys are drawn with equal possibility. For instance, say the guess is $g = 001$, then the Hamming distances are $H(001, 001) = 0$, $H(001, 010) = 2$, $H(001, 011) = 1$, $H(001, 000) = 1$, and $H(001, 111) = 2$. It follows that the entropy is $E = -\left[\frac{1}{5}\log(\frac{1}{5})+\frac{2}{5}\log(\frac{2}{5})+\frac{2}{5}\log(\frac{2}{5})\right]$. A superior guess would be $g = 000$ or $g = 111$, which actually maximizes the entropy. There will be multiple guesses that maximize the entropy, and finding any of them is enough.
While I can iterate over all compatible guesses $000, 001, \cdots, 110, 111$ to find the best guess, I'm sure there exists a more efficient solution? I have tried constructing the guess one-bit-at-a-time, but it doesn't always return the optimal guess.