Problem on algorithm theory Good morning everyone, I came across this interesting problem. Have been trying to solve it with the help of the binary search, but but it helped determine the number to within 16, which is not enough to solve the problem. Do you have any ideas?
Each of the two sisters made a natural number from 1 to 1000. Dad takes turns asking the sisters (one or the other) questions that can be answered "yes" or"no". He wants to ask each of the sisters no more than 6 questions to find out whether it is true that the hidden numbers differ by more than 500. At the same time, none of the girls knows what the other one has made, so each sister can only be asked about her number. Think of a way for dad to achieve his goal.
 A: I'm assuming you get $6$ questions for each girl, $12$ total, otherwise this seems tricky.
Let $X$ be the first sister's number and let $Y$ be the second sister's number.
Begin by asking the first sister a series of $5$ binary-search questions to estimate $X$. This will give you an interval $[a,b]$ which contains either $31$ or $32$ possibilities for $X$.
There is a corresponding interval of almost the same length - either $[a+501, b+500]$ or $[a-500,b-501]$, whichever makes sense - such that if we know $Y$, and it falls in that interval, we're not sure if $|X-Y| > 500$ or not. Let's assume $a < b \le 500$ without loss of generality so that this interval is $[a+501, b+500]$.
So now ask the second sister a series of $6$ binary search questions to distinguish between the following possibilities:


*

*$Y \le a+500$.

*$Y$ is each of the possible values in $\{a+501, a+502, \dots, b+500\}$.

*$Y \ge b+501$.


This is doable, because there are $33$ or $34$ possibilities here, and binary search can distinguish between up to $64$ possibilities.
If $Y \le a+500$, then we're done: $|X-Y| \le 500$, no matter what, because $X \ge a$. Similarly, if $Y \ge b+501$, then we're done: $|X-Y| > 500$, no matter what, because $X \le b$. 
Otherwise, we've determined the exact value of $Y$. So the last question to the first sister can be: is $|X-Y| \le 500$? (This is a concrete question, since we know what $Y$ is.)
