29 Jan
2004
29 Jan
'04
6:42 p.m.
On Tue, Jan 27, 2004 at 03:29:40PM -0400, MCKAY@vax2.concordia.ca wrote:
Twenty questions provides 20 bits. What if you know that at most k of the answers may be wrong?
http://math.berkeley.edu/~desj/thesis/thesis.pdf gives a complete answer for this particular question, via computer search. According to the table on page 38 of that thesis, with 20 questions and k possible lies, you can distinguish the following number of different possibilities: k | answers ---+-------- 0 | 1048576 1 | 49932 2 | 4968 3 | 776 4 | 154 5 | 28 6 | 4 Peace, Dylan