Consider the following puzzle:

> 
> * I have just flipped $n$ fair coins.
> * Before I start revealing them to you, you can ask me one yes/no question.
> * Then, you can make $n$ Head/Tail guesses.
> * What's your question and strategy for maximizing the number of correct guesses?
> 
> 
> 

The baseline (no question asked a priori) is to guess only H (or T). This will give you $\dfrac{n}{2}$ correct guesses (in expectation).

A first question would be: *"Is the first coin H?"*. If yes, guess only H, otherwise guess only T. So you now get $1 + \dfrac{n-1}{2} = \dfrac{n}{2} + \dfrac12$ correct guesses.

Another question: *"Are there more H than T?"* -- and just answer H or T depending on the answer. This strategy yields $n\cdot \Pr(H \geq T) = n\cdot\sum\_{k=n/2}^{n} \binom{n}{k} \cdot \dfrac{1}{2^n}$ correct guesses (from Binomial PMF), which is the best so far.

---

My questions are the following:

* How much more can we maximize the number of correct guesses? Is there a (tractable) way to quantify this (an upper bound)?
* One yes/no question means one bit of entropy. Can we derive some sort of relationship between this quantity and the *max* correct guesses? For example, if one asks two questions (2 bits of entropy), how much better off are we? Clearly, if we're allowed $n$ bits of entropy, then we can *guess* the entire sequence.