7
$\begingroup$

I am thinking of a number between 1 and 5000. It is the product of two primes. I tell my brother the larger of those primes, and to my sister the smaller.

You are allowed to ask each of us questions, first to my brother, then to me, then to my sister, and so on in turns, which we will always respond truthfully and honestly. Our answers will only be "Yes", "No", or "I don't know".

At most how many questions do you need to guess correctly the number I am thinking of?

Improve this question
$\endgroup$
2
  • $\begingroup$ I assume answers should also contain a strategy for question-asking? $\endgroup$
    – bobble
    Jan 17, 2021 at 0:01
  • $\begingroup$ At most, or at least? $\endgroup$
    – risky mysteries
    Jan 17, 2021 at 0:35

3 Answers 3

Reset to default
7
$\begingroup$

It can be done in

8

and that is optimal.

First, to best exploit their giving three-way answers we must ask three-way questions. For example, let's assume we have narrowed one of the factors down to 3,5 or 7. Then we would ask "I'm thinking of either 4 or 6. Is your factor larger?"; answer "no" means 3, "don't know" means 5 and "yes" means 7. This can be adapted to express any three-way split we want of the remaining possibilities.

Optimality:

Assume the smaller factor is 2. Then there are 366 possibilities for the larger factor and we can only use OP's or their brother's answers to find it. As 3^5 < 366 we need to ask them at least 6 questions and given the scheduling we also have to ask the sister at least 2 questions. Therefore we can't do better than 8.

Schedule:

There are 19 possibilities for the smaller factor S and 366 for the larger factor L. For the first question split the 366 into A+B+243 (smallest to largest). The exact sizes of A and B do not matter as long as neither is >81. If we end up in A or B we can spend 3 of the remaining 7 questions on S and 4 on L. Otherwise L will be >=691 leaving only 2,3,5 and 7 for S, so we can split 2 questions for S, 5 for L.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Somewhat interestingly, the question format would work even if the answerers were mind readers; when you say "I'm thinking of either 4 or 6", you actually aren't :-) (Also, I like the "schedule" part being compact to the point of being terse, but I find that opening up the logic a bit more tends to be well accepted by the voting populace here) $\endgroup$
    – Bass
    Jan 17, 2021 at 13:49
  • $\begingroup$ @Bass Not always in the mood to chase every single vote. Sometimes I'm content to write for those who can appreciate ;-) I'm not sure I follow the mind reading bit, are you saying I'm thinking of both at the same time or something? Sorry to be daft. $\endgroup$
    – Paul Panzer
    Jan 17, 2021 at 16:38
4
$\begingroup$

This is an improvement to Alemin's strategy that makes the maximum number of questions...

9

Because

It is possible to split the remaining possible numbers in 3 instead of 2 by using the fact that you can get 3 different answers, "yes", "no" and "I don't know".

So if I want to guess a number between 0 and 8 inclusive, I first split the range in 3 by choosing two numbers, 3 and 6. Then I ask:

"If there is an unknown number n >= 3, is your number x greater than or equal to either n or 6?"

If the answer is "yes", x must be >= 6. If the answer is "I don't know", x must be 3 <= x < 6. If the answer is "no", x must be < 3.

This means that we only need to ask the sister 3 questions because log3(19) = 2.68... and we need to ask for the big prime 6 times because log3(373) = 5.39... which means a total of 9 questions.

Improve this answer
$\endgroup$
3
$\begingroup$

Intresting question! Just to fix an upper bound:

14

Because:

The smallest prime number that your sister could have it's 2 so the biggest prime number that your brother could have it's 2477 (it' the biggest prime <2500).

There are 367 primes 2<=p<=2477, now I remember a famous game of guessing a number between 1 and 100 with 7 questions by recursively splitting the interval in half ("- <50? -No, - <75? -Yes, etc..."), so we could apply the same method by appropriately splitting the list of 367 primes using 9 questions.

we could apply the same method on the number you tell at your sister, her number is the smaller prime so it is <= to the biggest prime less or equal to sqrt(5000)=70,71... an this is 67. There are 19 primes<=67, so we need 5 or less questions to guess her number.

To guess the bigger prime (P) I will ask 5 times at your brother and 4 at you, to guess the smaller prime (p) I will ask 4 times at your sister and 1 at you in this order:

(Brother-you-sister): PPp, PPp, PPp, PPp, Pp-end.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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