# The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Author Message
bonanova
Daedalian Member

 Posted: Mon Aug 17, 2009 12:45 am    Post subject: 1 With 3 yes-no questions you can determine which of eight items, numbered 1 through 8, was chosen at random by a friend. Suppose there are nine objects numbered 1-9, and you may create multiple replicas of any or all of them. Can you now determine the number on an object chosen at random from the expanded set of objects, with an average of 3 yes-no questions?_________________ Vidi, vici, veni.
Trojan Horse
Daedalian Member

 Posted: Mon Aug 17, 2009 1:18 am    Post subject: 2 Seems to be too easy. Let me know if I missed a trap: Make three extra replicas of the 9. So you'll have four 9's, and one of everything else. First question: is the number a 9? If the answer is yes, you've done it in one question. Otherwise, you use three more questions to pick out the number from the remaining 8 possibilities; you'll use a total of four questions. There are 12 objects, and 4 of them have 9's. So you have a 1/3 chance of needing 1 question, and a 2/3 chance of needing 4 questions. Overall, you'll need 3 questions on average. In fact, by increasing the number of 9's, you can make the average as close to 1 as you want (but you can't actually reach 1).
bonanova
Daedalian Member

 Posted: Mon Aug 17, 2009 9:58 am    Post subject: 3 No trap. In fact for the case of one 1, two 2's, three 3's ... nine 9's you can get it with an average of exactly 3 guesses and no fewer. Should be no problem to see how. That's the answer I thought would be found; yours is much simpler. So - if with 9 we can get the average arbitrarily close to 1 question, we should be able to go past 9 for 3 questions. Is there an upper limit?_________________ Vidi, vici, veni.
ralphmerridew
Daedalian Member

 Posted: Mon Aug 17, 2009 12:48 pm    Post subject: 4 No upper limit. With objects numbered 1 through 1+2^k, create m=r*2^k copies of the 1. First ask "Is the number 1?", then use standard methods. Probabity m/(m+2^k) will take 1 questions. Probability (2^k)/(m+2^k) will take 1+k questions. On average, (m + (1+k)*2^k)/(m+2^k) questions needed == (r*2^k + (1+k)*2^k)/(r*2^k + 2^k) == (r+k+1)/(r+1) == 1 + k/(r+1) Which can be made arbitrarily close to 1.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year by All usersbonanovaralphmerridewTrojan Horse Oldest FirstNewest First
 All times are GMT Page 1 of 1

 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
You cannot post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum