bonanova Posted May 23, 2012 Report Share Posted May 23, 2012 You can guess a number between 1 and 1,000,000 with 20 yes/no questions. This owes to the fact that any positive integer not greater than one million can be represented using 20 binary digits, and you can determine them, one per question. In general, N questions will determine any positive integer not larger than 2N. Better results can be had if it is known that some numbers are more likely than others to be the target to be guessed. If nines and higher are removed from a deck of cards [counting Aces low] 3 guesses would determine the value [1-8] of a randomly chosen card. [but not the suit.] If the nines were added, a 4th guess would be needed. But suppose the numbers had different likelihoods of being chosen. This would be the case if the deck [ignoring suits] comprised 1 Ace, 2 deuces, 3 treys ... 8 eights and 9 nines. Can you determine a guessing strategy [a series of yes/no questions] that on average would determine the value of a card chosen at random from such a deck, in three guesses? Quote Link to comment Share on other sites More sharing options...
0 kevink2 Posted May 23, 2012 Report Share Posted May 23, 2012 The basic goal is to cut the space in half with each guess. So the first question is is the card 7 or higher (21 cards are 6 or lower, 24 are 7 or higher) If the card is 7 or higher, the the next 2 questions are is it 9 and is it 8 (if both answers are "no", then it's a 7) If the card is 6 or lower, Ask if the card is 5 or 6. This cuts the space in half(ish) again. Out of the 21 cards that are 6 or lower, 11 are 5 or 6. If the card is 5 or 6, use your last question to see if it's 5 (and if not, you know it's 6). If the card is 4 or lower (and we only have one more guess), ask if it's 4 (since we have the most of them). If it is, we are good. If not, just guess 3 (we have 3 3's and 3 aces and dueses, so you have a 50/50 change). In all there is a 100% chance to guess all cards 4 or higher (which is 39/45 of the time). In the other 6/45 times we get it right 50% of the time. The overall average for this is 42/45 times we get it right. Quote Link to comment Share on other sites More sharing options...
0 BobbyGo Posted May 23, 2012 Report Share Posted May 23, 2012 (edited) A couple of questions: Can the questions be dependant on the answers to previous questions? ...or do they need to be the same questions irrespective of previous answers? If the answer to Question A is Yes, then ask Question B. If the answer to Question A is No, then ask Question C. Can each question contain multiple conditions (using standard logic operators)? ...or would they need to be counted as separate questions? Does A = 1 AND B = 0? Does B = 1 OR C = 1? The best so far is to to ask a true/false for each of the last three binary digits. Convert each answer to 2N where N corrolates each question with its respecive binary digit (the same as you would if there were only 8 different numbers). Add the 3 values together. If the end result is 2 - 7, then that is the value of the number. If it is a 0, then the number is 8. If it is a 1, then the number is either a 1 or a 9. Assume all ones are nines (they are 9x more likely to be correct). This should be correct 44/45 times. Edited May 23, 2012 by BobbyGo Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted May 23, 2012 Author Report Share Posted May 23, 2012 The basic goal is to cut the space in half with each guess. So the first question is is the card 7 or higher (21 cards are 6 or lower, 24 are 7 or higher) If the card is 7 or higher, the the next 2 questions are is it 9 and is it 8 (if both answers are "no", then it's a 7) If the card is 6 or lower, Ask if the card is 5 or 6. This cuts the space in half(ish) again. Out of the 21 cards that are 6 or lower, 11 are 5 or 6. If the card is 5 or 6, use your last question to see if it's 5 (and if not, you know it's 6). If the card is 4 or lower (and we only have one more guess), ask if it's 4 (since we have the most of them). If it is, we are good. If not, just guess 3 (we have 3 3's and 3 aces and dueses, so you have a 50/50 change). In all there is a 100% chance to guess all cards 4 or higher (which is 39/45 of the time). In the other 6/45 times we get it right 50% of the time. The overall average for this is 42/45 times we get it right. Hi kevink2, welcome to the Den. You're on the right track. find how many guesses each number requires using your method and weight by likelihood of occurrence. A couple of questions: Can the questions be dependant on the answers to previous questions? ...or do they need to be the same questions irrespective of previous answers? If the answer to Question A is Yes, then ask Question B. If the answer to Question A is No, then ask Question C. Can each question contain multiple conditions (using standard logic operators)? ...or would they need to be counted as separate questions? Does A = 1 AND B = 0? Does B = 1 OR C = 1? The best so far is to to ask a true/false for each of the last three binary digits. Convert each answer to 2N where N corrolates each question with its respecive binary digit (the same as you would if there were only 8 different numbers). Add the 3 values together. If the end result is 2 - 7, then that is the value of the number. If it is a 0, then the number is 8. If it is a 1, then the number is either a 1 or a 9. Assume all ones are nines (they are 9x more likely to be correct). This should be correct 44/45 times. Any yes/no question is permitted. The question can have multiple parts; the answer can have only one part. It can depend on previous answers. Quote Link to comment Share on other sites More sharing options...
0 superprismatic Posted May 23, 2012 Report Share Posted May 23, 2012 Question 1: Ask if the third binary bit (the 4's place) of the number is 1. Question 2: Ask if the two low-order binary bits are the same. Question 3: If the answer to 1 and 2 are both NO, ask if the number is 9; otherwise, ask if it's even. (Yes,Yes,Yes) => the number is 4 (Yes,Yes,No) => the number is 7 (Yes,No,Yes) => the number is 6 (Yes,No,No) => the number is 5 (No,Yes,Yes) => the number is 8 (No,Yes,No) => the number is 3 (No,No,Yes) => the number is 9 (No,No,No) => the number is either 1 or 2 In the last case, one more question is needed (Is the number a 1?). So, with probability (42/45), 3 guesses are needed; with probability (3/45), 4 guesses are required. So, on average, the number of guesses will be 3*(42/45) + 4*(3/45) = 3.0666666...... Quote Link to comment Share on other sites More sharing options...
0 phil1882 Posted May 23, 2012 Report Share Posted May 23, 2012 somehow based on bonanova's past riddles i suspect binary isn't really integral to the problem. oh, its something to be considered of course, and i'm betting it helps explain the answer, however... the goal in my opinion is to try to get as many right in the fewest number of guesses. by that mean we need to be able to know its 9 is two guesses, such that the other guesses, even though take four, give an average of 3. so my first question would be... is the number 8 or 9? clearly this is will garantee knowing a large percentage of the result right off the bat. 17/45 in two guesses is the number 7 or 6? 13/45 in three guesses is the number 5 or 4? 9/45 in four guesses is the number 3? 3/45 in four guesses, and 3/45 in 5. doing this brings the percentage down to 3.0222... Quote Link to comment Share on other sites More sharing options...
0 bushindo Posted May 23, 2012 Report Share Posted May 23, 2012 You can guess a number between 1 and 1,000,000 with 20 yes/no questions. This owes to the fact that any positive integer not greater than one million can be represented using 20 binary digits, and you can determine them, one per question. In general, N questions will determine any positive integer not larger than 2N. Better results can be had if it is known that some numbers are more likely than others to be the target to be guessed. If nines and higher are removed from a deck of cards [counting Aces low] 3 guesses would determine the value [1-8] of a randomly chosen card. [but not the suit.] If the nines were added, a 4th guess would be needed. But suppose the numbers had different likelihoods of being chosen. This would be the case if the deck [ignoring suits] comprised 1 Ace, 2 deuces, 3 treys ... 8 eights and 9 nines. Can you determine a guessing strategy [a series of yes/no questions] that on average would determine the value of a card chosen at random from such a deck, in three guesses? Here's one that gives an expected value of 3 The questions that you need to ask are illustrated in the image below. For every node of the tree, a vertical bar ( | ) separates the available choices into 2 groups. For instance, for the first node, the question you can ask is: "Is the number equal to 7, 8, or 9?". An answer of 'Yes' would then take you to the right branch, and 'No' would take you to the left. Repeat the process until we reach a terminal node. Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted May 24, 2012 Author Report Share Posted May 24, 2012 Question 1: Ask if the third binary bit (the 4's place) of the number is 1. Question 2: Ask if the two low-order binary bits are the same. Question 3: If the answer to 1 and 2 are both NO, ask if the number is 9; otherwise, ask if it's even. (Yes,Yes,Yes) => the number is 4 (Yes,Yes,No) => the number is 7 (Yes,No,Yes) => the number is 6 (Yes,No,No) => the number is 5 (No,Yes,Yes) => the number is 8 (No,Yes,No) => the number is 3 (No,No,Yes) => the number is 9 (No,No,No) => the number is either 1 or 2 In the last case, one more question is needed (Is the number a 1?). So, with probability (42/45), 3 guesses are needed; with probability (3/45), 4 guesses are required. So, on average, the number of guesses will be 3*(42/45) + 4*(3/45) = 3.0666666...... Oh so close ... ! But guessing binary digits seems doomed. somehow based on bonanova's past riddles i suspect binary isn't really integral to the problem. oh, its something to be considered of course, and i'm betting it helps explain the answer, however... the goal in my opinion is to try to get as many right in the fewest number of guesses. by that mean we need to be able to know its 9 is two guesses, such that the other guesses, even though take four, give an average of 3. so my first question would be... is the number 8 or 9? clearly this is will garantee knowing a large percentage of the result right off the bat. 17/45 in two guesses is the number 7 or 6? 13/45 in three guesses is the number 5 or 4? 9/45 in four guesses is the number 3? 3/45 in four guesses, and 3/45 in 5. doing this brings the percentage down to 3.0222... Grouping is the right idea, need better groups. Here's one that gives an expected value of 3 The questions that you need to ask are illustrated in the image below. For every node of the tree, a vertical bar ( | ) separates the available choices into 2 groups. For instance, for the first node, the question you can ask is: "Is the number equal to 7, 8, or 9?". An answer of 'Yes' would then take you to the right branch, and 'No' would take you to the left. Repeat the process until we reach a terminal node. Bingo. Quote Link to comment Share on other sites More sharing options...
0 omthkkr Posted May 25, 2012 Report Share Posted May 25, 2012 The Binary search algorithm would prove effective here. Start from the center..i.e, is it higher than 5? Then, depending on the answer, go for the next center,like this, we can arrive at the answer in 3 steps, irrespective of the number of each denomination of the cards in the deck. Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted May 25, 2012 Author Report Share Posted May 25, 2012 The Binary search algorithm would prove effective here. Start from the center..i.e, is it higher than 5? Then, depending on the answer, go for the next center,like this, we can arrive at the answer in 3 steps, irrespective of the number of each denomination of the cards in the deck. But 2 x 2 x 2 = 8, and there are 9 options. The algorithm needs to use the information that some options are more likely than others. Quote Link to comment Share on other sites More sharing options...
Question
bonanova
You can guess a number between 1 and 1,000,000 with 20 yes/no questions.
This owes to the fact that any positive integer not greater than one million can
be represented using 20 binary digits, and you can determine them, one per
question. In general, N questions will determine any positive integer not larger
than 2N.
Better results can be had if it is known that some numbers are more likely than
others to be the target to be guessed. If nines and higher are removed from
a deck of cards [counting Aces low] 3 guesses would determine the value
[1-8] of a randomly chosen card. [but not the suit.] If the nines were added,
a 4th guess would be needed.
But suppose the numbers had different likelihoods of being chosen. This
would be the case if the deck [ignoring suits] comprised 1 Ace, 2 deuces,
3 treys ... 8 eights and 9 nines. Can you determine a guessing strategy
[a series of yes/no questions] that on average would determine the
value of a card chosen at random from such a deck, in three guesses?
Link to comment
Share on other sites
9 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.