Subj: RE: [math-fun] twenty questions
Twenty questions provides 20 bits. What if you know that at most k of the answers may be wrong? John
Very fun! I really like the "Uncommon knowledge about..." addenda, where, for example, it reported its belief that the sun is an insect, paper clips are used in Oriental cooking, etc. "It taint what you don't know, but what you know that taint so." --Mark Twain (supposedly)
MCKAY@vax2.concordia.ca wrote: What if you know that at most k of the answers may be wrong?
Another variant: this weekend I (foolishly) tried to impress my son by guessing his number from 1..100 in <=7 queries. After "50?-Less", "25?-Less" he said "This is boring. If I give you the same answer 3 times in a row you lose." Now what's the best strategy? Eg after 50?-Less should I guess 25? with a 50% chance of being forced to guess 1? next, or would it be better to guess, say, 12? next, skewing the interval search in return for a better chance of avoiding the probably-wasted forced guess? Given an optimal Guesser, what numbers are the Hider's best choices? (Perhaps posed as casino games: ante $1, the house pays $100 for a hit on the first guess, then reduces the payoff by half (rounded down) each time it answers...)
Another variant: this weekend I (foolishly) tried to impress my son by guessing his number from 1..100 in <=7 queries. After "50?-Less", "25?-Less" he said "This is boring. If I give you the same answer 3 times in a row you lose."
Now what's the best strategy?
An infinite version of the game is easy to analyse. Here, one picks a real number in some interval; the guesser tries to shrink the interval containing the number as quickly as possible, but mustn't allow three consecutive same answers. So, if the last two answers were the same, the guesser must waste a guess, to ensure the opposite answer. If the last two answers were different, he splits the interval according to the golden ratio (GR), so that the new answer is more likely to be different from the last answer. If he gets the different answer, he has reduced the interval by GR; if he gets the same answer, he has reduced by GR^2, but must waste a guess. Either way, he reduces by GR per guess. In the finite game (1..N), you never quite waste a guess, so you should converge faster. The roundoff errors likely have a lesser effect. Furthermore, you can start right in the middle. Anyway, 1+ceil(log_GR(N/2)) guesses should be enough. For N=100, that's 1+ceil(8.13)=10. For the 1..100 game, a quick computation shows that if one - starts with 50, - guesses the safe extremum when necessary, and otherwise - rounds the GR split to the nearest integer, then one always wins within eight guesses, and the average (over all 100 games) is 6.49 guesses. I don't mean to say that that's optimal, but it might be close.
(Perhaps posed as casino games: ante $1, the house pays $100 for a hit on the first guess, then reduces the payoff by half (rounded down) each time it answers...) I'd average $5.06 payoff ($4.06 profit) per game.
Given an optimal Guesser, what numbers are the Hider's best choices? That makes a difficult game-theory problem. If I knew that Hider would pick one of my 8-guess numbers (according to the strategy above), I'd shift to a slightly different strategy which gets those numbers sooner. But he knows I'd do that, and so... There are _so_ many Guesser strategies: the payoff matrix might be practically unconstructable, never mind solvable.
-- Don Reble djr@nk.ca
What do you do if the interval is (-oo, oo) on the real line? Does this change things in any meaningful way? What is the relationship of this game to continued fractions? At 09:01 AM 1/29/2004, Don Reble wrote:
An infinite version of the game is easy to analyse. Here, one picks a real number in some interval; the guesser tries to shrink the interval containing the number as quickly as possible, but mustn't allow three consecutive same answers.
So, if the last two answers were the same, the guesser must waste a guess, to ensure the opposite answer.
If the last two answers were different, he splits the interval according to the golden ratio (GR), so that the new answer is more likely to be different from the last answer. If he gets the different answer, he has reduced the interval by GR; if he gets the same answer, he has reduced by GR^2, but must waste a guess. Either way, he reduces by GR per guess.
=Henry Baker <hbaker1@pipeline.com>
What do you do if the interval is (-oo, oo) on the real line? Does this change things in any meaningful way?
Don't think so. As Don points out, the most significant effect is quantization in discrete v. I believe that the
What is the relationship of this game to continued fractions?
At 09:01 AM 1/29/2004, Don Reble wrote:
An infinite version of the game is easy to analyse. Here, one picks a real number in some interval; the guesser tries to shrink the interval containing the number as quickly as possible, but mustn't allow three consecutive same answers.
So, if the last two answers were the same, the guesser must waste a guess, to ensure the opposite answer.
If the last two answers were different, he splits the interval according to the golden ratio (GR), so that the new answer is more likely to be different from the last answer. If he gets the different answer, he has reduced the interval by GR; if he gets the same answer, he has reduced by GR^2, but must waste a guess. Either way, he reduces by GR per guess.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
=Henry Baker What do you do if the interval is (-oo, oo) on the real line? Does this change things in any meaningful way?
Don't think so; don't you just guess 0 first? As Don points out, domain quantization is probably more significant than domain size. In a casino version I think the round-off would constitute a not-inconsequential house "vigorish".
What is the relationship of this game to continued fractions?
Generally, "continued-f" expansions alternate excreting a spoor of integral floor(x), and transforming the residue: x-->f(x-floor(x)). When f is multiplying by B it gives base-B expansions, reciprocating give continued fractions, squaring first gives continued surds, etc. I suspect the no-three-in-a-row constraint is more akin to "base" Zeckendorf expansion than it is to continued fractions.
=Don Reble [...] Nice analysis, Don, thanks!
"John" == MCKAY <MCKAY@vax2.concordia.ca> writes:
John> Twenty questions provides 20 bits. What if you know that at John> most k of the answers may be wrong? There's a nice paper on this by Gacs, Dhagat, Spencer and Winkler: http://www.cs.bu.edu/faculty/gacs/papers/liars.ps.gz -- Victor S. Miller | " ... Meanwhile, those of us who can compute can hardly victor@idaccr.org | be expected to keep writing papers saying 'I can do the CCR, Princeton, NJ | following useless calculation in 2 seconds', and indeed 08540 USA | what editor would publish them?" -- Oliver Atkin
At 3:29 PM -0400 1/27/04, MCKAY@vax2.concordia.ca wrote:
Twenty questions provides 20 bits. What if you know that at most k of the answers may be wrong?
20 / (k+1) is a lower bound. Is it bigger than a breadbox? Is it bigger than a breadbox? Is it bigger than a breadbox? ... :) Paul
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
participants (7)
-
Don Reble -
dpt＠lotus.bostoncoop.net -
Henry Baker -
Marc LeBrun -
MCKAY＠vax2.concordia.ca -
Paul R. Pudaite -
victor＠idaccr.org