If this is your first visit, be sure to check out the
FAQ by clicking the link above. You may have to
register or
login before you can post: click the register link above to proceed. To start viewing messages, select the forum that you want to visit from the selection below.
| 23 APR 2004 at 7:33pm |
| Deleted User | The "smartest" possible question is one which will eliminate half of all possibilities. Let's look at this idea first. You might have a question which could eliminate 95% of all possibilities. For instance, using the "movie stars" category as an example, you could ask "Has this person starred in a movie released in 2004?" An answer of "yes" would eliminate 95% of the possible movie stars. However an answer of "no" would only eliminate 5% of the possibilities. Following this logic, the "best" question will always eliminate half of the possibilities.
This means that if you only ask one question, there must be two possibile answers to "guarantee" that you don't hit the correct answer. If you ask two questions, there must be four possibilities, half of which you will eliminate to leave two guesses on your final question. Carry this series onward and you quickly see the obvious progression.
Thus in order to assure that the guesser never has better than a 50% chance of guessing the correct answer, there must be 2^20 or 1,048,576 possibile answers in the given category in order to assure that the guesser needs a little luck to win.
|
| 23 APR 2004 at 8:18pm |
| Deleted User | Great answer, BacardiJim! You nailed it! An information-theoretic approach that proves that you have to have to choose from a VERY big set of possibilities to stand a chance against 20 smart questions.
Knowing this, if anyone told you they were thinking of a secret number between one and one million, given 20 questions you can always find it. Your first question could be "is it less than half a million", and based on the answer you'd then ask "is it less than a quarter of a million" or "is it less than three quarters of a million" depending on the first answer, and so on... Maybe you could amaze someone you know that isn't so good in math with this simple fact. Let them select a number between 1 and 1000 (actually, up to 1024 would be ok) and you can find it in only 10 guesses, using the same idea. A number between 1 and 100 takes only 7 attempts. If the topic was movie stars, I suppose 100 actors would be a fair upper estimate of the possible answers. The problem would be to find the appropriate near-50/50 questions to find the answer in less than half of your questions...
The same tactics will enable you to find any entry in a phone book of one million numbers in less than 20 attempts (one attempt being to flip to any page and look at any name in the hope that it's the right one). In fact, knowing the alphabet and something about the statistical distribution of letters in your language, and given a phone book with names ordered alphabetically makes it worth the risk to split every search in other than (roughly) 50/50 halves, since the probability of reducing the smaller, unfavorable part would be pretty small. For instance, if you're looking for the number of Aaron Aaronson, you'd be pretty stupid to flip to the middle of the catalogue and start looking there, even though the "dumb" 50/50 split binary search wouldn't result in that many more attempts anyway.
Pretty obvious stuff I suppose... :
|
| 24 APR 2004 at 12:24am |
MichalNGrand Inquisitor
Posts : 7058
Joined: 14 SEP 2003
Status : Online | Originally Posted By Petter_Holmberg (23 APR 2004 8:18pm)
Maybe you could amaze someone you know that isn't so good in math with this simple fact.
Not my friends - they all heard of binary search
I forgot my sig.
|
| 24 APR 2004 at 1:04am |
| Deleted User | And mine all watch The Price is Right. lol
|
| 24 APR 2004 at 8:56pm |
| Deleted User | Hehe, I see you need to choose who you hang out with carefully. :
So, does anyone know how to select the median of an unsorted set in linear time? It's not a very obvious trick...
|
