10
$\begingroup$

This question already has an answer here:

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.

$\endgroup$

marked as duplicate by SQB, JonMark Perry, Beastly Gerbil, IAmInPLS, Wu33o Sep 26 '16 at 8:08

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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.

$\endgroup$
  • 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 Sep 25 '16 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 Sep 25 '16 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.

$\endgroup$
  • 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 Sep 25 '16 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 Sep 25 '16 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 Sep 25 '16 at 15:43
  • $\begingroup$ Regarding your example, how would it change, when the secret number is 11, not 12? $\endgroup$ – Matsmath Sep 25 '16 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 Sep 25 '16 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.

$\endgroup$
  • $\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 Sep 25 '16 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 Sep 25 '16 at 15:53
  • $\begingroup$ And to you too :-) $\endgroup$ – Rand al'Thor Sep 25 '16 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 Sep 26 '16 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 Sep 26 '16 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.

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

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

$\endgroup$
  • $\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 Sep 25 '16 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 Sep 25 '16 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 Sep 25 '16 at 18:07
  • 1
    $\begingroup$ Exercise left for the reader. =) $\endgroup$ – dbanet Sep 25 '16 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 Sep 25 '16 at 18:15

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