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
Source: RMM 2021/2
Tags: RMM, number theory
13.10.2021 12:21
The answer is two questions. We shall first prove that this is enough: Sergey gives Xenia the sets $S_1=\{17,18\}$ and $S_2=\{17,19\}.$ Since $a_{17},a_{18}$ and $a_{19}$ are distinct, he receives two sets $S'_1$ and $S'_2$ with precisely one common element. By the definition of $S_1$ and $S_2,$ however, that common element is none other than $a_{17}.$ Since Sergey knows $a_{17}$ he now looks at $S'_1\setminus\{a_{17}\}$ and $S'_2\setminus\{a_{17}\}$ in order to find $a_{18}$ and $a_{19}$ as well. Now, Sergey knows the residues of $N$ modulo $17,18$ and $19$ respectively and by the Chinese Remainder Theorem, only one number smaller than $\gcd(17,18,19)=5814$ satisfies the said congruences, which is $N.$ Hence, two questions suffice. $\square$ We now prove that one question is not enough. Claim: For any positive integers $N$ and $N'$ there exist positive integers $a_1,a_2,...,a_{20}$ such that $N\equiv a_i\pmod{i}$ and $N'\equiv a_{\pi(i)}\pmod{i}$ for any $i\in\{1,2,...,20\}$ and some permutation $\pi\neq\text{id}\in S_{20}.$ Proof: We first do some optimization. It is clear that $\{a_1,a_2,...,a_{20}\}$ are uniquely determined by $\{a_9, a_{16}, a_5,a_7,a_{11},a_{13},a_{17},a_{19}\}.$ Hence, it is enough to show that the claim is true for those eight indices only. Furthermore, for simplicity, let $S=\{16,9,...,19\}.$ Now, for each $s\in S,$ let $x_s$ and $x'_s$ be the residues of $N$ and $N'$ respectively modulo $s.$ Now, consider the following pairs: $(16,9), (5,7), (11,13)$ and $(17,19).$ We will define $a_{16},a_9,...,a_{19}$ as such: for each pair $(m,n)$ choose $a_m$ and $a_n$ to be distinct from the previously chosen numbers (i.e. big enough) and to satisfy the following congruences:\[\begin{cases}a_m\equiv x_m\pmod{m} \\ a_m\equiv x'_n\pmod{n}\end{cases} \begin{cases}a_n\equiv x'_m\pmod{m} \\ a_n\equiv x_n\pmod{n}\end{cases}\]which can be done, by the Chinese Remainder Theorem. Finally, observe that $N, N'$ and $a_9,a_{16},...,a_{19}$ satisfy our claim for the permutation $\pi=(9,16,7,5,13,11,19,17),$ or in other words, the permutation $\pi$ which swaps $a_m$ and $a_n$ for each pair $(m,n).$ Therefore, the claim is true for the generator set, so it also holds for $\{a_1,a_2,...,a_{20}\}. \ \square$ Assume that Xenia chooses $N$ and $a_1,a_2,...,a_{20}$ which satisfy the above claim. By asking only one question, Sergey simply gets some $a_{i_1},a_{i_2},...,a_{i_k}$ and he knows that for some $\sigma\in S_{20},$ for $t\in\{1,2,...,k\}, \ N\equiv a_{i_{\sigma(t)}}\pmod{i_t}.$ But by our claim, $\sigma$ can be both $\text{id}$ and $\pi$ and hence, Sergey can never know is Xenia chose $N$ or $N'.$ So one question is not enough. Therefore, by combining this with the fact that two questions suffice, the desired answer is two. $\square$
13.10.2021 17:59
Two moves is sufficient. An example of a two-move strategy is to ask \[ S_1 = \{17,20\}, \qquad S_2 = \{19,20\} \]which determines $N$ modulo $17 \cdot 19 \cdot 20 = 6460 > 5000$. We proceed to show no single move $S$ is sufficient. Let us say that the numbers $11$, $13$, $16$, $17$, $19$ are big, and the other fifteen numbers are small. The lcm of the small numbers is exactly $2520 = 2^3 \cdot 3^2 \cdot 5 \cdot 7$. We consider two cases: If $S$ has a single number, then the task is clearly impossible. Then suppose $S = \{s_1, \dots, s_n\}$ where $n > 1$. Then, Xenia constructs $t_1$, \dots, $t_n$ such that \[ t_1 \equiv t_2 \equiv \dots \equiv t_n \equiv 1 \pmod{2520} \]and such that, whenever $s_i$ is big (indices modulo $n$), \[ t_i \equiv 1 \pmod{s_i}, \qquad t_{i+1} \equiv 2521 \pmod{s_i}. \]Then the set $\{t_1, \dots, t_n\}$ is a possible response corresponding to both $N = 1$ and $N = 2521$. Hence Xenia wins.
13.10.2021 18:00
Nice problem! 1. For the part that $2$ moves are sufficient, my construction is the same as the above one. The motivation is the following: it would be nice for Sergey to know the numbers explicitly, i.e. corresponding to their indices. The only way to do that is to choose sets {$x, y$} and {$y, z$}. Now Sergey knows the residue of $N$ modulo $lcm(x, y, z)$ (and it would be nicer if they are pairwise coprime, so as to apply CRT). In order for $N$ to have only one option, we should choose $xyz>5000$. Now it's easy to choose the three numbers. 2. $1$ move isn't sufficient. It's again same as most of the constructions, but I will write the motivation for it. Let Sergey choose the set {$s_1, s_2,...,s_m$}. Let Xenia gives him numbers $a_{s_i}$. We want to find two numbers $N'$ and $N''$, and two permutations of $s_1,s_2,...,s_m$ - $i'$ and $i''$, such that $N'=a_{i'}(mod s_{i'})$ and $N''=a_{i''}(mod s_{i''})$. So we want for each $j$, $a_{s_j}=N' (mod s_r)$ for some $r$ and $a_{s_j}=N''(mod s_t)$ for some $t$. Using generalized CRT, we want $d=N'-N''$ to be divisible by $gcd(s_r, s_t)$ for each possible choice of a pair of numbers from $1,2,...20$ (in order to ensure there is a solution for each $a_{s_j}$). We also want $d<5000$, so one good choice is $d=lcm(1,2,...,9,10)$, because the gcd of any two numbers from $1,2,...20$ divides $d$. Choose also $N'=1$ to ensure coprimity with $s_r$ (it's not necessary though), and we are only left to concreticise the permutations $i'$ and $i''$ - for example, let them be $i$ and $i+1$ for each $i=s_j$. Now the numbers $d+1$ and $1$ will both work, done.
13.10.2021 18:30
It would be interesting to see if there is a reasonable solution when $5000$ is replaced by $20000$.
14.10.2021 10:05
Solved with p_square Two questions works. To do this Sergey asks $\{20,19\}$ first and then $\{17,19\}$ next which gives him the values of $a_{17}, a_{19}, a_{20}$ and this uniquely determines $N$ since the lcm of $17,19,20$ is $6460 > 5000$. Now, a strategy for Xenia that shows one question wont work. She fixes two numbers $n$ and $n+2520$. Say the indices chosen by Sergey are $b_1, b_2, \cdots, b_m$. Xenia constructs the numbers ($z_i$) she responds with in the following way. $$z_i \equiv n \pmod{b_i}$$ $$z_i \equiv n+2520 \pmod{b_{i+1}}$$ This is possible since $2520$ is the lcm of stuff from $1$ to $10$ so any common factor of $b_i$ and $b_{i+1}$ also divides it. These indices may correspond to either $n$ or $n+2520$ and so one question is insufficient, as claimed. $\blacksquare$
24.10.2021 05:34
Solved with Jeffrey Chen, Kevin Wu, Nathan Cho. The answer is two moves. Proof two moves work: Sergey can choose the sets \(\{17,20\}\) and \(\{19,20\}\), uniquely determining \(N\) mod 17, 19, and 20, i.e.\ mod \(17\cdot19\cdot20=6460\) by Chinese remainder theorem. Proof one move fails: I contend Sergey cannot distinguish 1 and 2521. Suppose Sergey chooses the set \(S=\{s_1,s_2,\ldots,s_n\}\). Then Xenia replies with the set \(\{r_1,r_2,\ldots,r_n\}\) such that for each \(i=1,\ldots,n\) (with indices modulo \(n\)), \[r_i\equiv1\pmod{s_i}\quad\text{and}\quad r_i\equiv2521\pmod{s_{i+1}}.\]This is always possible since \(\gcd(s_i,s_{i+1})\mid2520\).
25.10.2021 16:04
Problem proposed by my friend Sergey Kudrya, the author of some nice number-theoretic problems on Russian competiotions
30.01.2022 03:40
30.01.2022 03:42
You guys are smart!!!
25.07.2022 05:58
I know this might be late⦠To be honest the answer and proof are all pretty simple,however,after I finished my solution and was going to write it down,I forgot the information that the integers are distinct,that would basically deny the solutions above(e.g.give{17,19},{17,20},you might get{1,2}&{1,2}),so I tried to fix my solution,and I managed to prove that without the information that all a are distinct,the minimal number of moves that have to be made is 3,it would be way harder to prove than the original one
17.08.2022 17:31
The answer is two. For a construction, first ask for $\{17,20\}$, then ask for $\{19,20\}$. The distinctness condition means we can find $a_{20}$, from which finding $a_{17}$ and $a_{18}$ is easy. Then from Chinese Remainder Theorem we can determine $N \pmod{17 \cdot 19 \cdot 20}$, which works since $17 \cdot 19 \cdot 20>5000$. We will now prove that one query is insufficient. Obviously, if $|S|=1$, then we can only determine $N \pmod{(\text{something}\leq 20)}$ which is insufficient. Otherwise, suppose $S=\{i_1,\ldots,i_n\}$. Xenia responds with $\{b_1,\ldots,b_n\}$ such that $b_k \equiv 1 \pmod{i_k}$ and $b_k \equiv 2521 \pmod{i_{k+1}}$, taking indices $\pmod{n}$. This is always possible since $\gcd(i_k,i_{k+1})<=10 \implies \gcd(i_k,i_{k+1}) \mid 2520$. If $a_{i_k}=b_k$ for all $k$, then $N=1$ is possible. If $a_{i_k}=b_{k-1}$ for all $k$, then $N=2521$ is possible, so by doing this Sergey cannot deduce the value of $N$. $\blacksquare$
04.01.2024 03:54
So somehow, I managed to misread the question badly into a form where $2$ queries is possible but much harder (if even possible) to show that $1$ query is impossible. So here's a nice problem: Quote: Xenia and Sergey play the following game. Xenia thinks of a positive integer $N$ not exceeding $5000$. Then she fixes $20$ not necessarily distinct positive integers $a_1, a_2, \dots, a_{20}$ such that, for each $k = 1,2,\cdots,20$, $a_k$ is the remainder when $n$ is divided by $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, where any new set he asks must be disjoint from previous sets. How many moves does Sergey need to determine for sure the number Xenia thought of?
The answer is two queries; Sergey can use $\{17, 20\}$ and $\{19, 20\}$, as the distinctness condition means he is able to distinguish $N$ mod $20$ and thus $N$ mod 17 and 19. By CRT he can then distinguish $N$ uniquely. For proof of sufficiency, just note that Sergey cannot distinguish $1$ and $2521$: given Sergey's query of $\{a_1, a_2, \dots, a_k\}$ with $k \geq 2$, Xenia can return $r_1, r_2, \dots, r_k$ with $r_i \equiv 1 \pmod {a_i}$ and $r_i \equiv 2521 \pmod {a_{i+1}}$ for each $i$. This is always possible as $\gcd(a_i, a_{i+1}) \mid 2520$.
29.01.2024 17:25
The answer is $2$ queries. For sufficiency, Sergey can query $\{20,19\}$ and $\{20,17\}$ to determine $N\pmod{6460}$, which clearly uniquely determines $N$. For necessity, suppose for the sake of contradiction that Sergey can query a set $s_1<s_2<\dots <s_k$ which is guaranteed to determine $N$. To counter this, Xenia can make $a_i\equiv 1\pmod{s_i}$ and $a_i\equiv 2521\pmod{s_{i+1}}$, with indices taken mod $k$. Such $a_i$ always exists by CRT as $\gcd (s_i,s_{i+1})\mid 2520$. Since there is no bound on the $a_i$, Xenia can always ensure distinctness. This construction guarantees Xenia a victory, as Sergey's information could lead to $N=1$ or $N=2521$.
31.01.2024 01:20
2 i guess
23.11.2024 07:39
This problem felt really weird, and I initially thought the proof that 1 query was insufficient was easier than it actually is. After quite a bit of fakesolving, I managed to figure everything out. We claim that the answer is 2 queries. First, to see why 1 query is insufficient, note that if $|S|=1$ Sergey can know what one of the terms is but this gives Sergey what $N$ is $\pmod{r}$ for some $r\le 20$ which is not sufficient to determine $N$. If Sergey queries the set $s_1<s_2<\dots<s_k$, it is possible that the set chosen by Xenia was such that $a_i \equiv 1 \pmod{s_i}$ and $a_i\equiv 2521 \pmod{s_{i+1}}$ which must exist since $\gcd{s_i,s_{i+1}} \mid 2520$ (only primes less than 11 have more than one multiple less than 20). But then, Sergey cannot distinguish 1 and 2521, so 1 query is clear insufficient. Now, to determine $N$ in 2 queries, Sergey follows the following algorithm. He selects the sets ${19,17}$ and ${19,16}$. Since each term is distinct, the only common term in the replies must be $a_{19}$. Sergey can then determine $a_{19}$, and use that to know that the other terms are $a_{17}$ and $a_{16}$ respectively. Now, Sergey knows $N \pmod{19}$ , $N \pmod{17}$ and $N \pmod{16}$. Then, by the Chinese Remainder Theorem, Sergey can also determine $N \pmod{5168}$ which since $N<5168$ allows Sergey to determine exactly what $N$ is.