(Optional) A prize is randomly placed in one of ten boxes, numbered from 1 to 10

Question

(Optional) A prize is randomly placed in one of ten boxes, numbered from 1 to 10. You search for the prize by asking yes-no questions. Find the expected number of questions until you are sure about the location of the prize, under each of the following strategies. a) An enumeration strategy: you ask questions of the form "is it in box k?” (b) A bisection strategy: you eliminate as close to half of the remaining boxes as possible by asking questions of the form "is it a box numbered less than or equal to k?"

Explanation / Answer

Solution:

a) The probability of getting it right on the first guess is 1/10
The probability of getting it right on the SECOND guess is 9/10 * 1/9 = 1/10
The probability of getting it right on the THIRD guess is 9/10 * 8/9 * 1/8 = 1/10
...
so you see the pattern, the probability of getting it correct on any given try is the same: 1/10

So the expected number of guesses is:

1/10 * (1 + 2 + 3 ... + 8 + 9 + 10) = 1/10 * (10*11 / 2) = 11/2 = 5.5

b) Probability for 3 guesses:

2/5 + 3/5 * 1/3 = 2/5 + 1/5 = 3/5

probability for 4 guesses:
3/5 * 2/3 = 2/5 (no surprise should be whatever's leftover from above...this is a check that indicates our reasoning is correct).

So the answer would be:

3 * 3/5 + 4 * 2/5 = (9 + 8)/5 = 17 / 5 = 3.4 guesses

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.