Sequences of Coin Flips, Hamming Cubes, and Ultrafilters
Published:
My colleagues and I were discussing the following probability brain teaser at lunch: Suppose I have a fair coin and I use it to write down a 100-character sequence of heads and tails. I don’t show this process to you at all nor tell you any part of the sequence but you are allowed to ask me one yes/no question which I’ll answer truthfully. Then, you will write down your own 100-character sequence with the goal of maximizing the number of matches between our sequences. e.g. if my sequence is $THH…$ and you submit $HTH…$, the first two are not a match but the third is. What yes/no question would you ask and what would you then submit (and why)? What is the expected value of your strategy?
