10
$\begingroup$

Your best friend (Bob) comes to you with this problem.

The Problem

His teacher (Mr. Sam) will ask Bob to work out a number in his head between 1 and 27.
Bob has to find the correct number, by asking Mr. Sam three Yes/No questions about the number.
Mr. Sam can respond with 3 different answers: "Yes", "No", or "I do not know".

Example:

If the number is 12

Is it an even number? Yes.
Is it divisible by 9? No.
If I take a random number between 10 to 15, will I get the right number? I do not know.

Find the strategy, so every number between 1 to 27 can be guessed correctly.

Improve this question
$\endgroup$
8
  • $\begingroup$ For the third example, if the number is lower than 10 or bigger than 15, Mr Sam will answer No $\endgroup$
    – Jamal Senjaya
    Commented Sep 25, 2016 at 15:16
  • $\begingroup$ Possibly related: Differentiate between the numbers from 1 to 5 with one single yes/no question $\endgroup$
    – Rand al'Thor
    Commented Sep 25, 2016 at 15:21
  • $\begingroup$ Ok, bed time, I will check this this puzzle tomorrow morning. $\endgroup$
    – Jamal Senjaya
    Commented Sep 25, 2016 at 15:28
  • $\begingroup$ I just solved it! :-) $\endgroup$
    – Rand al'Thor
    Commented Sep 25, 2016 at 15:30
  • $\begingroup$ Congrats, this question is currently #1 on the Hot Network Questions. $\endgroup$
    – Rand al'Thor
    Commented Sep 25, 2016 at 16:32

6 Answers 6

Reset to default
13
$\begingroup$

We can solve this puzzle simply by using the solution to this question three times, once for each digit of the ternary representation of $n$, which is defined to be one less than Mr Smith's number and is therefore a number between 0 and 26, or between 000 and 222 in ternary form.

  • Q1:

    "I'm thinking of a number: either 0 or 1. Is the sum of this number with the units digit of the ternary representation of $n$ greater than 1?"

    • If the units digit is 0, the answer is "no".
    • If the units digit is 1, the answer is "I don't know".
    • If the units digit is 2, the answer is "yes".

  • Q2:

    "I'm thinking of a number: either 0 or 1. Is the sum of this number with the threes digit of the ternary representation of $n$ greater than 1?"

    • If the threes digit is 0, the answer is "no".
    • If the threes digit is 1, the answer is "I don't know".
    • If the threes digit is 2, the answer is "yes".

  • Q3:

    "I'm thinking of a number: either 0 or 1. Is the sum of this number with the nines digit of the ternary representation of $n$ greater than 1?"

    • If the nines digit is 0, the answer is "no".
    • If the nines digit is 1, the answer is "I don't know".
    • If the nines digit is 2, the answer is "yes".

After these three questions, Bob knows the number.

Improve this answer
$\endgroup$
2
  • 6
    $\begingroup$ The only problem with this answer is that if you ask an average teacher any one of those questions, they'll stare blankly back at you and ask "What?" $\endgroup$
    – ArtOfCode
    Commented Sep 25, 2016 at 17:26
  • 1
    $\begingroup$ @ArtOfCode Well, yeah. This particular teacher seems to have an unusual level of interest in his subject though, otherwise he wouldn't have devised such an exercise for Bob. (Hey, are you joining the home-ed camp? :-) ) $\endgroup$
    – Rand al'Thor
    Commented Sep 25, 2016 at 17:30
23
$\begingroup$

Ask:

I'm thinking of a number between 9 and 18. Is it greater than or equal to your number?

  • If the number is between 1 and 9:

    He will answer yes. If his number is between 1 and 8 my number is bigger. If his number is 9, then my number is bigger or equal to his.

  • If the number is between 19 and 27:

    He will answer no, since his number is definitely larger and not equal to mine.

  • If the number is between 10 and 18:

    He will answer I don't know. If my number is 9 the answer would be no, and if my number is equal to his the answer would be yes, so for every number both possibilities exist.

The next two questions

have the same form, dividing the remaining range into three parts each time. By the end we will have narrowed down the possible numbers from 27 to 27/3 = 9, to 9/3 = 3, to 3/3 = 1.

For example, with the number 12:

I'm thinking of a number between 9 and 18. Is it greater than or equal to your number? I don't know
Therefore his number is greater than 9 and less than or equal to 18 (from 10 to 18 inclusive)
I'm thinking of a number between 12 and 15. Is it greater than or equal to your number? Yes
Therefore his number is less than or equal to 12 (from 10 to 12 inclusive)
I'm thinking of a number between 10 and 11. Is it greater than or equal to your number? No
Therefore his number is greater than 11 (from 12 to 12 inclusive),
And therefore the number must be 12.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ This is also a neat solution. Similar idea to mine, but we've approached the problem in different ways: you by splitting the range of possibilities, I by considering the ternary representation. The advantage of my approach is that it uses only integers and not arbitrary real numbers; the advantage of yours is that it's probably more visually intuitive. $\endgroup$
    – Rand al'Thor
    Commented Sep 25, 2016 at 15:34
  • $\begingroup$ @randal'thor I started off using integers, but realized that it wouldn't work for the last case where the range of the center interval is 1; then my 'random' number is known and we can't get 'I don't know'. I'm hoping that by thinking more carefully about the boundary conditions I can get back to using integers. $\endgroup$
    – 2012rcampion
    Commented Sep 25, 2016 at 15:37
  • $\begingroup$ Oh no... your solutions both seem more elegant than mine, and posted faster too! :( And here I thought for once I'd be the first to answer SOMETHING. $\endgroup$
    – Xenocacia
    Commented Sep 25, 2016 at 15:43
  • $\begingroup$ Regarding your example, how would it change, when the secret number is 11, not 12? $\endgroup$
    – Matsmath
    Commented Sep 25, 2016 at 17:18
  • 1
    $\begingroup$ @Matsmath The teacher's answer would be 'I don't know' since my number could be 10 (not greater than or equal to 11) or 11 (equal to 11); then I'd know his number must be between 11 and 11. $\endgroup$
    – 2012rcampion
    Commented Sep 25, 2016 at 17:49
3
$\begingroup$

With some cooperation from the professor, we could apply...

the solution to this puzzle three times.

The way we approach it is to ask the professor:

If the number is between 1 to 9, it is in group 1. If 10 to 18, group 2. If 19 to 27, group 3.
If I flipped as many coins as the group number of your number, will 2 of them be the same?

If it is in group 1, he has to say no. Group 2, he won't know. Group 3, he has to say yes. Repeat the question, narrowing the group ranges accordingly.

Sorry for the wall of text but I can't seem to get the spoiler blockquote to work properly.

Improve this answer
$\endgroup$
5
  • $\begingroup$ My solution also involves using the solution to that puzzle 3 times, but (hopefully) in a more intuitive way, applying it directly to each ternary digit rather than to groups of numbers. $\endgroup$
    – Rand al'Thor
    Commented Sep 25, 2016 at 15:48
  • $\begingroup$ Yeah, I had to digest your answer a bit and have to agree it IS easier to get. +1 to you, dammit. $\endgroup$
    – Xenocacia
    Commented Sep 25, 2016 at 15:53
  • $\begingroup$ And to you too :-) $\endgroup$
    – Rand al'Thor
    Commented Sep 25, 2016 at 16:41
  • $\begingroup$ I submitted an edit to try and break up your wall of text. In general, do what you normally would to break up paragraphs, but add a >! to the beginning of each line, and a ` ​ ` (two spaces) to the end. $\endgroup$
    – Schism
    Commented Sep 26, 2016 at 6:53
  • $\begingroup$ @Schism: thanks! I tried that, but what kept happening was that I'd end up with block-quoted, non-hidden text which was prefaced with an exclamation mark. Must have been doing something wrong, because what you helped me edit was precisely what I was trying to do in the first place. $\endgroup$
    – Xenocacia
    Commented Sep 26, 2016 at 6:55
2
$\begingroup$

Bob tells Mr. Sam

that there's a hypothetical computer program called Hyp.  Mr. Sam secretly inputs his number into Hyp. Bob can input two sets into Hyp. If the secret number is in the first set, Hyp displays a $0$. If it's in the second set, Hyp displays a $1$. And if it's in neither Hyp randomly displays either a $0$ or a $1$.

Bob's first question is then: "if I input 1 to 9 as the first set and 10 to 18 as the second set, will Hyp display a $0$?" If Mr. Sam answers "yes" - his number's in the first set, "no" - it's in the second and "I don't know" - it's in 19 to 27.

Bob's second question is: "taking the first three numbers as the first set and the next three numbers as the second, will Hyp display a $0$?" This narrows it down to three numbers and the last question uses the first number as the first set and the next as the second set yielding the secret number.

Improve this answer
$\endgroup$
1
$\begingroup$

rand al'thor, 2012rcampion, Xenocacia, Paul Evans have answers correctly, here I give another way to answer correctly, without making Mr. Smith thinks too long. Even a kid can answer the questions.

I will create 3 pairs of list

First pair :
1A : 2,3,5,6,8,9,11,12,14,15,17,18,20,21,23,24,26,27
1B : 2,5,8,11,14,17,20,23,26

Then ask Mr. Smith : If I take a random list, Does the number in the list ?
If the answer is Yes then, write number 2 in first paper.
(because the number appears in both list)
If the answer is No then, write number 0 in first paper.
(because the number do not appears in both list)
If the answer is I do not know then, write number 1 in first paper.
(because the number only appears in one list)

then

2nd pair :
2A : 4,5,6,7,8,9,13,14,15,16,17,18,22,23,24,25,26,27
2B : 4,5,6,13,14,15,23,24,25

Then ask Mr. Smith : If I take a random list, Does the number in the list ?
If the answer is Yes then, write number 2 in the 2nd paper.
If the answer is No then, write number 0 in the 2nd paper.
If the answer is I do not know then, write number 1 in the 2nd paper.

then

3rd pair :
3A : 10 to 27
3B : 10 to 18

Then ask Mr. Smith : If I take a random list, Does the number in the list ?
If the answer is Yes then, write number 2 in the 3rd paper.
If the answer is No then, write number 0 in the 3rd paper.
If the answer is I do not know then, write number 1 in the 3rd paper.

then

put the number in the order 3rd 2nd 1st as base 3 number, than convert it into base 10 number, do not forget to add 1. The result is Mr. Smith number.

Improve this answer
$\endgroup$
0
$\begingroup$

The title explicitly mentions so called "Yes/No" questions, which, judging from the name, accept either a Yes or a No for an answer, however the question body also explicitly places an exhaustive set of possible answers, which is finite and of size $3$.

Therefore, since three questions are to be asked, a function $$f:\,Q\to R$$ with $|Q|=|R|=3$ describes some configuration $f$ of answers $r=f(q)$ to questions $q\in Q$, where $r\in R$, for all $q\in Q$.

Hence, the set $R^Q$ delivers all possible configurations.

Coincidentally, if $I=\left\{k\in\mathbb Z\,\,|\,\,1\leq k\leq27\right\}$ is the set of the integers to be guessed amongst, then $$\left|R^Q\right|=\left|I\right|,$$ which shows there exists at least one bijection from the set of all configurations of answers $R^Q$ to $I$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ If you read the question more carefully, the so-called Yes/No questions actually accept three possible answers: "Yes", "No", or "I don't know". $\endgroup$
    – Rand al'Thor
    Commented Sep 25, 2016 at 18:02
  • 1
    $\begingroup$ @randal'thor which is explicitly addressed in the second part of my first sentence, if you read it more carefully. $\endgroup$
    – dbanet
    Commented Sep 25, 2016 at 18:05
  • 2
    $\begingroup$ Sorry, missed that. But your answer only proves that it's possible to find a strategy, while the question asks you to actually find one. $\endgroup$
    – Rand al'Thor
    Commented Sep 25, 2016 at 18:07
  • 1
    $\begingroup$ Exercise left for the reader. =) $\endgroup$
    – dbanet
    Commented Sep 25, 2016 at 18:08
  • $\begingroup$ Bonus points exercise: if there exists at least one bijection between sets $A$ and $B$, show that there actually are $n!$ of them whenever $A$ and $B$ are finite, where $n=\left|A\right|$. $\endgroup$
    – dbanet
    Commented Sep 25, 2016 at 18:15

Not the answer you're looking for? Browse other questions tagged or ask your own question.