The game of Shafiqa and Habibi

Question

Shafiqa chose a positive integer number $X\le100$, and Habibi is trying to guess the number. Habibi can select two natural numbers $M$ and $N$ less than $100$ and ask about the greatest common divisor $\gcd(X+M,N)$ of $x+M$ and $N$.

Can Habibi always determine Shafiqa's number with at most seven questions?

Answer 1

Yes.

Why:

He first asks the values from $gcd(X+0,30)$ to $gcd(X+3,30)$. Two of $X,X+1,X+2,X+3$ are bound to be divisible by 2, and at least one is a multiple of 3. If none of them are divisible by 5, $X+4$ is, but whether it's the case or not he can then determine the $mod 2,3$ and $5$ values of $X$. Thus, there are 3 or 4 possible $X$ solutions in the form of $n, n+30, n+60$, with $n+90$ in the mix if possible. If he asks the GCDs of $X$ and these values starting from the last, he can either find the solution directly (the first answer equal to the number he picked) or by eliminating the rest after 3 more questions at most.

An alternative solution:

He first asks the values from $gcd(X+0,70)$ to $gcd(X+5,70)$, which allows him to determine the $mod 2,5$ and $7$ values of $X$. Thus, there are 1 or 2 possible $X$ solutions in the form of $n$ and $n+70$ if possible. If $n>29$, there's only one solution. Otherwise he asks the GCD of $X$ and $n+70$, after which he can either find the solution directly or by eliminating the rest.

Answer 2

Even I like the answer of Nautilus, I have a different approach.

In the very first round M isn't important, because you can swap M and X.

So I set M to 1 and want to get the most possible information out of the GCD-Answer. Like Nautilus I came to N = 30 (because of 2*3*5) to "filter" these prime numbers. But this is improvable. I can get out more information if I choose a number beyond 50. (50 because 1+50*z is at maximum 2 times a number from 1 to 100)

If I choose 30 I get 8 possible results for GCD(1+x, 30). For example N = 60 (2*2*3*5) or 72 (2*2*2*3*3) or 96 (2*2*2*2*2*3) would give me 12 different values.

This means: If I can build a binary search for the problem, I will find an answer within 6 rounds. This is a little bit complicated to explain (for me), but there are only 32 different possibilities where the GCD-answer is 1. And Sqrt(32) = 5.6568. This all counts only for the first round. Because if you can eliminate so much branches here, you can maybe get more information in the next rounds.

So first I think about an AI for this, but I don't want to overengineer and just bruteforced it with an algorithm to find a fingerprint in 6 rounds for all 100 X.

6 rounds: (M=1,N=40), (M=2,N=30), (M=3,N=40), (M=4,N=80), (M=5,N=27), (M=6,N=48) gives a fingerprint

This is not all. Because you can eliminate more numbers per round than only 50%, you can build a shorter fingerprint.

5 rounds: (M=1,N=40), (M=2,N=30), (M=3,N=40), (M=4,N=80), (M=6,N=48)

Answer 3

The answer is

Yes New starting point solves all within 5 guesses

We can achieve this by using a simple algorithm as follows

1. We try m=1,n=60, we eliminate all candidates that would've given a different gcd, or those that are not dividable by the gcd (after we add m).
2. We try m=2,n=60, once again we eliminating all candidates that don't fit.
3. we try m=3,n=60, once again eliminating all candidates that don't fit.
4. -5 We try the largest number left, each time eliminating all candidates that don't fit.

This works as proven by the following fiddle, which uses exactly this algorithm on all possibly starting numbers. (this fiddle is a bit more verbose, and prints all guesses for each number)