So according to my calculations, a game of 20 questions can distinguish 
between up to 1,048,576 things, assuming only yes/no questions.  Not bad...

-- 
Tim Cook
http://home.bellsouth.net/p/PWP-empyrean

-----BEGIN GEEK CODE BLOCK-----
Version: 3.12
GFA dpu- s: a?-- C++(++++) U P? L E--- W++(+++)>$
N++ o? K- w(+) O? M-(--) V? PS+(+++) PE(--) Y(--)
PGP-(--) t* 5++>+++++ X+ R* tv+ b++(+++) DI
D++(---) G(++) e*>++ h+ !r--- !y--
------END GEEK CODE BLOCK------

Post a reply to this message

> So according to my calculations, a game of 20 questions can distinguish 
> between up to 1,048,576 things, assuming only yes/no questions.  Not 
> bad...

Thinking up the actual questions to distinguish between 1048576 things is 
another matter though... ;-)

Post a reply to this message

That's just plain bad thinking all round. I assume you meant yes/no answers not
questions. I don't think yes/no as a question will help you identify anything
and of course there's no fixed number of questions, they can be different at
every level so you have many many many more permutations. Or is it just
fortunate that I've always picked something of that list! ;)

Post a reply to this message

MattM wrote:

> and of course there's no fixed number of questions, they can be different at
> every level so you have many many many more permutations. Or is it just
> fortunate that I've always picked something of that list! ;)

Au contrare... If 20 questions will be asked yielding 20 yes/no answers, 
than 2^20 things can be distinguished. The fact that the questions on 
one branch may or may not be the same as the ones on another branch is 
irrelevant. There are still the same number of branches. [Although 
obviously as a *practical* matter being able to have more relevent 
quenstions on the different branches helps a lot.]

Post a reply to this message

Question 1. Is it a fish?
Answer 1. Yes
Question 2. Is it a cat?
Answer 2. (Are you stupid?)

I think Question 1 (in this universe) usually drives question 2. So at the start
of the game Question 2 can still be anything as we don't know what the answer to
one is yet. In fact question 1 can be anything. (Are you Hilary Clinton? are you
an vegetable? Do your ears turn purple when listening to Pearl Jam?) So off the
bat we have '2^However many questions you can think of' and that's just
question 1.

Post a reply to this message

> [Although obviously as a *practical* matter being able to have more 
> relevent quenstions on the different branches helps a lot.]

You just need to think of a question that will exactly split the remaining 
outcomes in half each time.  For 2^3 or 2^4 items this is doable, but for 
2^20...

Post a reply to this message

scott wrote:
>> [Although obviously as a *practical* matter being able to have more 
>> relevent quenstions on the different branches helps a lot.]
> 
> You just need to think of a question that will exactly split the 
> remaining outcomes in half each time.  For 2^3 or 2^4 items this is 
> doable, but for 2^20...

Question: Is the set of possible outcomes recursively enumerable?

Post a reply to this message

No, next question. (Is this a game now?)

Post a reply to this message

Can a set exist that has a finite cardinal number and yet is not 
recursively enumerable?

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

I'm afriad that won't split this problem 50/50. That's the problem with this
game, sometimes yes/no is not enough. I really want to say, you're making an
assumption. Is your question even related? Who said anything about finite?

Post a reply to this message