Problem Statement
Your friend has a fair coin. They flip it \(100\) times consecutively and record the sequence of outcomes. Your goal is to guess the sequence that your friend flipped. You may ask a single Yes/No question to your friend to help you determine the sequence.
The maximum probability you can achieve of guessing your friend’s sequence is in the form \(a^{-b}\), where \(b\) is maximal. Find \(ab\).
Original Problem Link: Click here
Solution
Obviously, since we can only ask one Yes/No question, it makes sense to ask a question that gives us the most information possible.
At first thought, you might think asking for the value at a single position is optimal (which halves the search space). But interestingly, if we ask whether a certain set of \(n\) digits match a specific fixed sequence (say something like \(0101010011100\ldots\) \(n\) digits), we can achieve the same maximum reduction — and this is actually optimal.
Step 1: Structure of the Question
Suppose we fix \(n\) specific positions, and ask:
“Do the digits at these positions form exactly this particular sequence?”
The answer is either Yes or No.
What is the probability that the answer is Yes?
Since for those \(n\) positions, there are \(2^n\) possible combinations, and each is equally likely, the probability that the friend’s sequence matches exactly our chosen sequence is:
\[\mathbb{P}(\text{Yes}) = \frac{1}{2^n}\]Thus,
\[\mathbb{P}(\text{No}) = 1 - \frac{1}{2^n}\]Step 2: Finding the expression
Using total probability:
\[\mathbb{P}(\text{Correct}) = \mathbb{P}(\text{Correct} \mid \text{Yes}) \times \mathbb{P}(\text{Yes}) + \mathbb{P}(\text{Correct} \mid \text{No}) \times \mathbb{P}(\text{No})\]Step 3: Finding \(\mathbb{P}(\text{Correct} \mid \text{Yes})\)
If the answer is Yes, then we now know exactly what those \(n\) positions are.
Thus, we only need to correctly guess the remaining \(100-n\) positions.
Since each unknown position is independent and fair:
\[\mathbb{P}(\text{Correct} \mid \text{Yes}) = \frac{1}{2^{100-n}}\]Step 4: Finding \(\mathbb{P}(\text{Correct} \mid \text{No})\)
If the answer is No, then:
- Among the \(2^n\) possible combinations for the \(n\) positions, one sequence (the one we asked) is ruled out.
- Thus, there are \(2^n - 1\) possible combinations remaining for those \(n\) digits.
- For the other \(100-n\) digits, there are still \(2^{100-n}\) possibilities.
Therefore, the total number of possible full sequences is:
\[(2^n - 1) \times 2^{100-n}\]Hence, the probability of correctly guessing the entire sequence is:
\[\mathbb{P}(\text{Correct} \mid \text{No}) = \frac{1}{(2^n - 1) \times 2^{100-n}} = \frac{1}{2^{100-n}(2^n-1)}\]Step 5: Putting It All Together
Thus,
\[\mathbb{P}(\text{Correct}) = \frac{1}{2^{100-n}} \times \frac{1}{2^n} + \frac{1}{2^{100-n}(2^n-1)} \times \left(1 - \frac{1}{2^n}\right)\]Simplifying:
\[= \frac{1}{2^{100}} + \frac{1}{2^{100}} = \frac{2}{2^{100}} = \frac{1}{2^{99}}\]Thus, the maximum probability is:
\[2^{-99}\]Now, the problem asks for \(ab\) where the probability is \(a^{-b}\).
Here, \(a = 2\) and \(b = 99\), so:
Final Answer: The required value is \(\boxed{198}\)
💡 Did you enjoy this problem? Check out more puzzles in the Problems section!