Answer: A guessing game…

Here goes a long overdue answer to my previously posted puzzle ‘A guessing game‘.

Q1. What is the optimal strategy (best questions to ask) for a player? Optimal = the expected number of turns taken to correctly guess is minimized

Since the selection probability of each element is the same (=1/N), this problem becomes considerably easier. Let S_i be the set of possible elements at the beginning of your questions. We know that, after 1 round of questions (which ends either by getting a ‘No’ for answer, or reaching M number of questions), we will have it narrowed down to a subset of elements.

Since you have a maximum of ‘M’ questions, the number of possible different subsets of S_i you will get is ‘M+1′ (You might get a ‘No’ in the first ‘M-1″ questions, or you can divide the remaining subset to 2 by the ‘Yes/No response for the M-th question) .  Therefore, we can model these as an information source, and employ source coding results to obtain an answer.

• The element the opponent selected is the ‘information symbol’ to be transmitted. So we can assume there is a source with ‘N’ different source symbols.
• Since we can divide the set in to ‘M+1′ subsets with each round of questions, this resembles a source with an alphabet of size ‘M+1′.
• Each round of questions can be considered as a single character in a codeword.

Now the target is to find a source coding method, so that the average codeword length is minimized. That would give the most optimal questioning strategy, where the average number of question rounds taken is minimized. We know in source coding the lowest average codeword length we can obtain with an alphabet of ‘M+1′,  is ceil(log_M+1(N)).

Since the elements are equi-probable, the most optimal strategy would be dividing the set S_i in to M+1 equal subsets (Say S(1),S(2),…,S(M+1)). If the number of elements is not an integer multiple of ‘M+1′, we need to divide it the most evenly possible way, even if the number of elements in all the subsets aren’t the same.The questioning would go on as follows,

1. Does the selected element belong to S(2) or S(3) or …. or S(M+1) ?
2. Does the selected element belong to S(3) or S(4) or …. or S(M+1) ? and so on, where the k-th question is
k. Does the selected element belong to S(k+1) or S(k+2) or …. or S(M+1) ? (k=1,2,..M)

Getting a ‘No’ for the answer at the k-th step, will tel you that it’s in S(k).  Or if ye ‘M’ times it’s in S(M+1).

Q2. What is the maximum number of turns a player would need to arrive at the correct element?

If we employ the strategy mentioned  in Q1, we know that the player will arrive at the correct guess in ceil(log_M+1(N)) steps.

It’s similar to building a tree with ‘M+1′ branches at each node, until you cover all the elements.  We start with ‘S’, and the child nodes will be a partition of the parent node. And we proceed building the tree until we get only one element corresponding to each node.

Note.

1. ceil(.) is the ceiling function.

2. Here are few references on source coding and related concepts.

• http://en.wikipedia.org/wiki/Information_entropy
• http://en.wikipedia.org/wiki/Shannon%27s_source_coding_theorem
• Fundamentals of Information Theory and Coding Design, Roberto Togneri and C.J.S. deSilva

I’d appreciate if you’d let me know if you have a different solution or a different way to arrive at the solution. Or if there is anything wrong with this answer. :-)

A similar procedure can be done when the selection of elements are not equi-probable. I think along the line of ‘Huffman coding’ will help us get the optimal strategy.