MathDB

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

Problem Statement