Skip to content

Best guess of 100 tosses after one yes-no query

Question

A friend tosses a fair coin 100100 times and writes down the sequence. You may ask one question that the friend answers truthfully with yes or no, and then you must name the whole sequence. Your best achievable probability of being right has the form a−ba^{-b} with integers a,ba,b and bb as large as possible. Find abab.

Short answer

198198. Any yes/no question splits the 21002^{100} sequences into a set AA and its complement; you then guess within the indicated part, succeeding with probability ∣A∣2100⋅1∣A∣+2100−∣A∣2100⋅12100−∣A∣=2−99\tfrac{|A|}{2^{100}}\cdot\tfrac1{|A|}+\tfrac{2^{100}-|A|}{2^{100}}\cdot\tfrac{1}{2^{100}-|A|}=2^{-99}, whatever the question. So a=2a=2, b=99b=99.

Adapted from QuantQuestions.io; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question

Start with a free lesson: Probability Fundamentals is part of a free topic. Create a free account, no card needed, to read it in full with worked solutions.

Read it free