In information theory courses, Huffman coding is often presented as the optimal strategy for playing the classic parlor game of Twenty Questions. However, Thomas Cover observed the following caveat in the 1990s: Twenty Questions games always end with a reply of “Yes,” whereas Huffman codewords need not obey this constraint.
In this short and cute paper, John T. Gill III brings resolution to this issue, and proves that even in games of Twenty Questions, the relationship between the average number of questions and the entropy still remains the same. As Forrest Gump would say, “One less thing to worry about.”
Gill, John T.; Wu, William. Twenty Questions Games Always End With Yes.
Watch the best 20 Questions game ever: click here