9 replies to this topic

[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 2^N.

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?

[kevink2]

Spoiler for My Guess

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.

[BobbyGo]

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?

Spoiler for Possible answer

The best so far is to to ask a true/false for each of the last three binary digits. Convert each answer to 2^N 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, 23 May 2012 - 03:45 PM.

[bonanova]

Spoiler for My Guess

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.

Spoiler for to compute the average

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?

Spoiler for Possible answer

The best so far is to to ask a true/false for each of the last three binary digits. Convert each answer to 2^N 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.

[superprismatic]

Spoiler for - No, but I can get it down to an average of 3.066666... guesses:

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

[phil1882]

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

Spoiler for non-binary aproach

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

[bushindo]

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 2^N.

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

Spoiler for solution

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.

[bonanova]

Spoiler for - No, but I can get it down to an average of 3.066666... guesses:

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

Spoiler for non-binary aproach

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

Spoiler for solution

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.

[omthkkr]

Spoiler for My answer

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.

[bonanova]

Spoiler for My answer

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.