Design a strategy that minimizes the expected number of questions you will ask in the following 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. If you draw the tree instead of describing its construction, give a brief description of how you came up with it. 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}?" 

 

STEP1:

The deck of cards consists of one ace of spades, two deuces of spades, three threes and so on up to nine nines. So the deck consists of 45 cards in total. 

The probability to select a particular card is given by 

The two lowest values are added to get a new element, 1/45+2/45=3/45

That is, the probability to choose a card which is either an ace or deuce is 3/45

Now, there are eight elements. They are the ace-deuce set, the three, the four and so on, up to nine. The order of probability values for the remaining cards is 

3/45, 3/45, 4/45, 5/45, 6 /45, 7/45, 8/45 and 9/45

The two lowest values are added to get a new element, 3/45 +3/45 = 6/45

That is, the probability to choose a card which is either an ace or deuce or threes is 6/45 

The probability of aces, deuces and threes is 6/45 which is greater than the probabilities of either fours or fives. 

STEP2:

Now, the two lowest values are added to get a new element, 4/45 + 5/45 = 9/45

That is, the probability to choose a card which is either a five or a six is 9/45

Now, there are six elements. They are 

6/45,6/45, 7/45, 8/45, 9/45 and 9/45  

STEP3:

Now, the two lowest values are added to get a new element, 6/45 + 6/45 = 12/45

There are five elements remaining. They are 

7/45, 8/45, 9/45, 9/45 and 12/45  

STEP4:

Now, the two lowest values are added to get a new element, 7/45 + 8/45 = 15/45 

There are four elements remaining. They are 

9/45 ,9/45, 12/45 and 15/45 

STEP5:

Now, the two lowest values are added to get a new element, 9/45 + 9/45 = 18/45 

There are three elements remaining. They are 

12/45, 15/45 and 18/45 

STEP6:

Now, the two lowest values are added to get a new element, 12/45 + 15/45 = 27/45 

There are two elements remaining. They are 

18/45 and 27/45 

STEP7:

Now, the two lowest values are added to get a new element, 18/45 + 27/45 = 45/45 

The Huffman tree for the elements is given below

The strategy for minimizing the number of questions is to take the pairing in reverse order.

STEP8:

The first question that can be asked is "Is the card in the set of fours, fives and nines?" 

If the card is not present, then the card will be in the other set and the question can be "Is the card, a seven or eight?" 

If the card is not present, then the card will be in the other set and the question can be "Is the card in the set of ace, duce and three?" 

If the card is not present, the card picked can be guessed as six. 

If the card is present, questions can be continued until the card is guessed. 

If the card should be an ace or deuce then it will take five questions to pinpoint it. By dividing the elements as nearly as possible into halves for each question, four questions are required to guess if the card is three. 

Five questions are needed to guess an ace. Five are also needed to guess a deuce, but there are two deuces, which require 10 questions. The three call for three times four or 12 questions and so on up to nine. The total number of questions for all forty five cards is given by