Q2 Matemática  (Romanian Masters of Mathematics Collection 2021)

Xenia e Sergey jogam o seguinte jogo. Xenia pensa em um inteiro positivo $N$ não superior a $5000$. Então ela fixa $20$ inteiros positivos distintos $a_1,a_2,\cdots ,a_{20}$ tal que, para cada $k=1,2,\cdots ,20$, os números $N$ e $a_k$ são congruentes módulo $k$. Por um movimento, Sergey diz a Xenia um conjunto $S$ de inteiros positivos não superiores a $20$, e ela diz a ele de volta o conjunto $\{a_k:k\in S\}$ sem soletrar qual número corresponde a qual índice. De quantos movimentos Sergey precisa para determinar com certeza o número que Xenia pensou? Sergey Kudrya, Rússia