## Welcome to BrainDen.com - Brain Teasers Forum

 Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account. As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends. Of course, you can also enjoy our collection of amazing optical illusions and cool math games. If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top. If you have a website, we would appreciate a little link to BrainDen. Thanks and enjoy the Den :-)
Guest Message by DevFuse

# Guess the number, binary style

9 replies to this topic

### #1 bonanova

bonanova

bonanova

• Moderator
• 4784 posts
• Gender:Male
• Location:New York

Posted 23 May 2012 - 08:59 AM

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?
• 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

### #2 kevink2

kevink2

Newbie

• Members
• 7 posts

Posted 23 May 2012 - 03:33 PM

Spoiler for My Guess

• 0

### #3 BobbyGo

BobbyGo

Junior Member

• Members
• 96 posts
• Gender:Male

Posted 23 May 2012 - 03:35 PM

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?

Edited by BobbyGo, 23 May 2012 - 03:45 PM.

• 0

### #4 bonanova

bonanova

bonanova

• Moderator
• 4784 posts
• Gender:Male
• Location:New York

Posted 23 May 2012 - 05:00 PM

Spoiler for My Guess

Hi kevink2, welcome to the Den. You're on the right track.

Spoiler for to compute the average

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?

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.
• 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

### #5 superprismatic

superprismatic

Not just Prismatic

• Moderator
• 1196 posts
• Gender:Male

Posted 23 May 2012 - 06:52 PM

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

• 0

### #6 phil1882

phil1882

• Members
• 308 posts

Posted 23 May 2012 - 07:36 PM

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

• 0

### #7 bushindo

bushindo

Senior Member

• VIP
• 716 posts
• Gender:Male
• Location:Los Angeles, CA

Posted 23 May 2012 - 09:33 PM

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
Spoiler for solution

• 0

### #8 bonanova

bonanova

bonanova

• Moderator
• 4784 posts
• Gender:Male
• Location:New York

Posted 24 May 2012 - 08:15 AM

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

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

Grouping is the right idea, need better groups.

Here's one that gives an expected value of 3

Spoiler for solution

Bingo.
• 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

### #9 omthkkr

omthkkr

Newbie

• Members
• 8 posts

Posted 25 May 2012 - 12:08 PM

• 0

### #10 bonanova

bonanova

bonanova

• Moderator
• 4784 posts
• Gender:Male
• Location:New York

Posted 25 May 2012 - 04:16 PM

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.
• 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#### 0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users