bonanova Posted August 15, 2009 Report Share Posted August 15, 2009 You have nothing else to do so you write the numeral "1" on a ping pong ball. You enjoy the experience so much that your write "2" on two other balls. And "3" on three others, until you finally write "9" on nine more balls. Let's see, that's 45 balls in nine groups, each the size of their written numbers. Your friend offers to select one of them at random and let you guess its written number by asking a sequence of yes-no questions. You find the game unchallenging. Since 23 = 8 and 24 = 16 you can always guess the number in four tries - usually in three. Your friend asks you if there isn't a guessing strategy that will reduce the average number of questions needed determine the number on the selected ball? Quote Link to comment Share on other sites More sharing options...
0 bushindo Posted August 15, 2009 Report Share Posted August 15, 2009 On 8/15/2009 at 8:17 AM, bonanova said: You have nothing else to do so you write the numeral "1" on a ping pong ball. You enjoy the experience so much that your write "2" on two other balls. And "3" on three others, until you finally write "9" on nine more balls. Let's see, that's 45 balls in nine groups, each the size of their written numbers. Your friend offers to select one of them at random and let you guess its written number by asking a sequence of yes-no questions. You find the game unchallenging. Since 23 = 8 and 24 = 16 you can always guess the number in four tries - usually in three. Your friend asks you if there isn't a guessing strategy that will reduce the average number of questions needed determine the number on the selected ball? I got the following average number of questions, anyone got lower? Reveal hidden contents 3.044444 questions Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 15, 2009 Report Share Posted August 15, 2009 On 8/15/2009 at 8:51 AM, bushindo said: I got the following average number of questions, anyone got lower? Reveal hidden contents 3.044444 questions Reveal hidden contents I got 3.066666... questions (3/45 times you have to ask the fourth one) Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 15, 2009 Report Share Posted August 15, 2009 Reveal hidden contents I got 137/45 = 3.0444... My scheme gets the 4,5,6,8,9 in 3 guesses; the 7 in 2 guesses; the 3 in 4 guesses; and the 1 & 2 each in 5 guesses. Quote Link to comment Share on other sites More sharing options...
0 superprismatic Posted August 15, 2009 Report Share Posted August 15, 2009 (edited) Reveal hidden contents 138/45=3.06666667(Is it >7?, is it >5?, is it >3?...) Edited August 15, 2009 by superprismatic Quote Link to comment Share on other sites More sharing options...
0 superprismatic Posted August 15, 2009 Report Share Posted August 15, 2009 (edited) Reveal hidden contents 136/45= 3.022222222 (Is it >7? , No: Is it >5?, No: Is it >3?, No: Is it 3?, No: Is it 2?) Edited August 15, 2009 by superprismatic Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 15, 2009 Report Share Posted August 15, 2009 On 8/15/2009 at 4:24 PM, superprismatic said: Reveal hidden contents 136/45= 3.022222222 (Is it >7? , No: Is it >5?, No: Is it >3?, No: Is it 3?, No: Is it 2?) Reveal hidden contents You have 17 ask 2, 13 ask 3, 9 ask 4, 3 ask 4, 3 ask 5 Yours has a maximum of 5 questions. I can give the same answer with a maximum of 4 questions: Is it >= 7? (yes) Is it 9? - 9/45 ask 2 to get 9 Is it 8? - 15/45 ask 3 to get 7 or 8 (no) Is it >= 5? (yes) Is it 6? - 11/45 ask 3 to get 5 or 6 You have 1,2,3,4 left... Is it >= 3? Is it 4? - 7/45 ask 4 to get 3 or 4 Is it 2? - 3/45 ask 4 to get 1 or 2 So you have 9/45 asking 2, 26/45 ask 3, and 10/45 ask 4....136/45 Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted August 16, 2009 Author Report Share Posted August 16, 2009 The average can be still lower. Reveal hidden contents The optimum method requires in some cases 5 questions. Quote Link to comment Share on other sites More sharing options...
0 plainglazed Posted August 17, 2009 Report Share Posted August 17, 2009 Reveal hidden contents Exactly 3 questions on average asking four questions: Is it 5?, Is it even? Is it >7? Is it >2? Quote Link to comment Share on other sites More sharing options...
0 plainglazed Posted August 17, 2009 Report Share Posted August 17, 2009 Nevermind, Came up with that in the shower not fully awake (though usually where I do my best thinking, not fully awake that is). Realized my error on the drive into work. Rats. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 17, 2009 Report Share Posted August 17, 2009 (edited) Reveal hidden contents 3.0 Reveal hidden contents ...to divide 45 into successive number of equal parts and pick the balls that equal the sum.. In integer arithmetic, 45/2 = 22 (9+8+5) (45 - 22)/2 = 11 (7+4) (45 - 22 - 11)/2 = 6 (6) ..etc Avg = 0 1. Is it 9 or 8 or 5? (yes) 2. Is it 9? Avg += 2 * (9/45) (yes) Yay! It is 9! (no) 3. Is it 8? Avg += 3 * (13/45) (yes) Yay! It is 8! (no) Yay! It is 5! (no) 2. Is it 7 or 4? (yes) 3. Is it 7? Avg += 3 * (11/45) (yes) Yay! It is 7! (no) Yay! It is 4! (no) 3. Is it 6? Avg += 3 * (6/45) (yes) Yay! It is 6! (no) 4. Is it 3? Avg += 4 * (3/45) (yes) Yay! It is 3! (no) 5. Is it 2? Avg += 5 * (3/45) (yes) Yay! It is 2! (no) Yay! It is 1! Edited August 17, 2009 by methinks Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 17, 2009 Report Share Posted August 17, 2009 (edited) Ugh finally remember weighted trees Reveal hidden contents 9*2 + 9*3 + 15*3 + 6*3 + 3*4 + 5*3 ---------------------------------- 45 Average of exactly 3 questions... Reveal hidden contents Build a huffman tree: Is it 9,4,5? Yes: Is it 9? Yes: 2 questions to get 9 No: Is it 5? 3 questions to get 4 and 5 No: Is it 8 or 7? Yes: Is it 8? 3 questions to get 7 and 8 No: Is it 6? Yes: 3 questions to get 6 No: Is it 3? Yes: 4 questions to get 3 No: Is it 2? 5 questions to get 1 or 2 Edit: add code block Edited August 17, 2009 by tpaxatb Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted August 17, 2009 Author Report Share Posted August 17, 2009 On 8/17/2009 at 2:23 PM, tpaxatb said: Ugh finally remember weighted trees Reveal hidden contents 9*2 + 9*3 + 15*3 + 6*3 + 3*4 + 5*3 ---------------------------------- 45 Average of exactly 3 questions... Reveal hidden contents Build a huffman tree: Is it 9,4,5? Yes: Is it 9? Yes: 2 questions to get 9 No: Is it 5? 3 questions to get 4 and 5 No: Is it 8 or 7? Yes: Is it 8? 3 questions to get 7 and 8 No: Is it 6? Yes: 3 questions to get 6 No: Is it 3? Yes: 4 questions to get 3 No: Is it 2? 5 questions to get 1 or 2 Edit: add code block Bingo! Quote Link to comment Share on other sites More sharing options...
Question
bonanova
You have nothing else to do so you write the numeral "1" on a ping pong ball.
You enjoy the experience so much that your write "2" on two other balls.
And "3" on three others, until you finally write "9" on nine more balls.
Let's see, that's 45 balls in nine groups, each the size of their written numbers.
Your friend offers to select one of them at random and let you guess its written
number by asking a sequence of yes-no questions. You find the game unchallenging.
Since 23 = 8 and 24 = 16 you can always guess the number in four tries - usually in three.
Your friend asks you if there isn't a guessing strategy that will reduce the average
number of questions needed determine the number on the selected ball?
Link to comment
Share on other sites
12 answers to this question
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.