Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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.
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.
