Problem

Source: RMM 2021/2

Tags: RMM, number theory



Xenia and Sergey play the following game. Xenia thinks of a positive integer $N$ not exceeding $5000$. Then she fixes $20$ distinct positive integers $a_1, a_2, \cdots, a_{20}$ such that, for each $k = 1,2,\cdots,20$, the numbers $N$ and $a_k$ are congruent modulo $k$. By a move, Sergey tells Xenia a set $S$ of positive integers not exceeding $20$, and she tells him back the set $\{a_k : k \in S\}$ without spelling out which number corresponds to which index. How many moves does Sergey need to determine for sure the number Xenia thought of? Sergey Kudrya, Russia