Question

Design a strategy that minimizes the expected number of questions you will ask in the fol- lowing game. You have a deck of cards that consists of one one, two twos, three threes, and so on up to nine nines for a total of 45 cards. Someone draws a card from the shuffled deck and looks at its value (hiding it from you). The goal is to determine the value of the card through asking a series of questions, each of which must be answerable with “yes” or “no” (such as “Is the card a nine?”).

To answer this question, you should express your strategy as a decision tree. You may either explicitly draw the decision tree or describe its construction in sufficient detail so that I could draw it from your description.

Furthermore, briefly explain why this minimizes the expected number of questions you will ask in this game. You are not required to give a formal proof.

Hint: The first question to ask in the optimal decision tree is “Is the card one of {4, 5, 9}?” Equivalently, the question can be “Is the card one of {1, 2, 3, 6, 7, 8}?”

Answer 1

To minimize the number of questions to be asked to find the correct card we have two divide them into groups so that the number of questions can be reduced.Here we will do pairing

P(1)=1/45

P(2)=2/45

P(3)=3/45

P(4)=4/45

P(5)=5/45

P(6)=6/45

P(7)=7/45

P(8)=8/45

P(9)=9/45

The pairing should be done on the basis of probability of occuring less of a particular card.So first 1 and 2 will be paired .So the probability of occuring 1 and 2 will be 3/45.Now we have 8 divisions .Further we pair (1,2),(3) .Probability of occur 1 ,2,3 is 6/45 and so on we will reach to last step as shown in pic below.We are  doing pairing because the number of steps will be reduced and the the number of question to be asked to get correct answer will be reduced.

Now whenever any question is asked we can start from bottom and get to the correct answer in the number of steps shown in the picture.

Now if some question is asked like 9 will occur we need to ask only 2 question .

in this way we can minimize the questions to be asked