(see book, p.123, problem 19) A prize is randomly placed in one of ten boxes, nu

Question

(see book, p.123, problem 19) 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 the following strategies (a) An enumeration strategy: you ask questions of the form "is the prize 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 the prize in a box numbered less than or equal to k?"

Explanation / Answer

a)

Here, there is a possibility that we might get to know as to in which box is the price in the first guess itself or it might take all the 10 boxes to get the prize.

Probability that you get it right on the first guess=1/10, second guess=9/10*1/9, third guess=9/10*8/9*1/8. We would get 1/10 for any of the cases. Hence, we get 1/10*(10*11/2)=11/2=5.5.

b)

Probability for three guesses= 2/5 + 3/5 * 1/3 = 2/5 + 1/5 = 3/5

Probability for 4 guesses= 3/5 * 2/3 = 2/5

Hence, the final answer would be 3 * 3/5 + 4 * 2/5=3.4

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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