Jump to content
BrainDen.com - Brain Teasers
  • 0

Guess the number, binary style


Question

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 post
Share on other sites

9 answers to this question

Recommended Posts

  • 0

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.

Link to post
Share on other sites
  • 0

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 by BobbyGo
Link to post
Share on other sites
  • 0

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.

Link to post
Share on other sites
  • 0

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......

Link to post
Share on other sites
  • 0

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...

Link to post
Share on other sites
  • 0

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.

post-14842-0-18745700-1337805036_thumb.j

Link to post
Share on other sites
  • 0

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.

post-14842-0-18745700-1337805036_thumb.j

Bingo. post-1048-0-31202300-1337843611.gif

Link to post
Share on other sites
  • 0

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.

Link to post
Share on other sites
  • 0

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.

Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...