A game involving divisibility

77 Views Asked by At

Two players $A$ and $B$ play the following game. First $A$ fixes a natural number $N > 100$ but does not reveal it. Afterwards $B$ chooses another natural number $n > 1$ and asks $A$ whether $n$ divides $N$. If yes, $B$ wins. If $n > N$, $A$ wins. If no-one won already, the game starts from the beginning with $N$ replaced by $N - n$. Does player $B$ have a winning strategy if it's forbidden to name the same number $n$ more than once?

If the second player consecutively asks for $n = 2$, $5$, $6$, $10$, $12$, $3$, $13$, $4$, $14$, $18$, $39$, $21$, $27$, $51$, $36$, $28$, $23$, $83$, $137$, $173$, $9$*, he will surely win provided that $N \le 3 \cdot 10^6$. How to find the smallest integer $N$ which won't be detected by these $n$? Does it exist?

* the smallest $N$ for which it's necessary to ask $1, 2, 3, \ldots$ questions are $101$, $101$, $101$, $101$, $101$, $105$, $105$, $105$, $105$, $165$, $189$, $201$, $225$, $261$, $345$, $381$, $561$, $669$, $705$, $885$ - these are computer checked.