Problem 2039

Solution:

The answer to both requests of the exercise is two questions. To completely solve the exercise it suffices to exhibit a method for determining the combination in two questions, and to show that, even knowing that the different number is zero, one question is not sufficient. For illustrative purposes, we will also give a simpler method to solve specifically part (a).

In what follows, we will denote by $u$ and $d$ the values of the equal number and of the different number respectively, and by $t$ the index of the different number (that is, $x_{t}=d$ and $x_{i}=u$ for $i \neq t$). Given a question $y_{1}, \ldots, y_{2016}$, we observe that the answer is $\left(\Sigma-y_{t}\right) u+y_{t} d$, where $\Sigma$ denotes the sum of the numbers of the question $y_{1}+\cdots+y_{2016}$.

METHOD FOR PART (a).
As the first question, we submit to the machine the numbers $1, \ldots, 1$. In this way the machine will answer $2015 u$, from which we can obtain the value of $u$. Now we still need to figure out what the index $t$ is. The second question is $1,2,3, \ldots, 2016$. We obtain the answer $(\Sigma-t) u$, with $\Sigma=1+2+\cdots+2016$. Observing that $u$ cannot be zero (because the two numbers of the combination are different), it is immediate to obtain $t$.

ONE QUESTION IS NOT ENOUGH.
We must show that for every possible question there exist two different combinations that give the same answer. Consider a question $y_{1}, \ldots, y_{2016}$ (with sum $\Sigma$). If two of these numbers are equal to each other, $y_{i}=y_{j}$, then the two combinations that have equal number 1 and different number 0 in position $i$ and $j$ respectively produce the same answer. Hence we may assume that the numbers of the question are all different. In particular, we can take $i \neq j$ such that $y_{i}$ and $y_{j}$ are different from $\Sigma$. Suppose that the combination is $x_{i}=0$ and $x_{k}=\Sigma-y_{j}$ for $k \neq i$. The answer, then, would be $\left(\Sigma-y_{i}\right)\left(\Sigma-y_{j}\right)$. One sees that the combination with $i$ and $j$ swapped ($x_{j}=0$ and $x_{k}=\Sigma-y_{i}$ for $k \neq j$) would give the same answer.

METHOD FOR PART (b).
The first question is $1,-1,1,-1, \ldots$, and we call $R$ the answer. We observe that, setting $\Delta=u-d$, we have $R=(-1)^{t} \Delta$. Now we choose the second question $y_{1}, \ldots, y_{2016}$ in such a way that:
(1) the numbers $R$ and $\Sigma=y_{1}+\cdots+y_{2016}$ are coprime (and $\Sigma$ is nonzero);
(2) the numbers $y_{i}(-1)^{i}$ are pairwise non-congruent modulo $\Sigma$.
For example, these conditions are satisfied by choosing $y_{1}=1$ and $y_{i}=|R| i$ for $i>1$ (note that $\Delta \neq 0$, hence $R \neq 0$). The answer that we obtain, then, is
$$R' = (\Sigma-y_{t}) u + y_{t} d = \Sigma u - y_{t} \Delta = \Sigma u - y_{t}(-1)^{t} R \text{.}$$
From this answer we can deduce the class of $y_{t}(-1)^{t} R$ modulo $\Sigma$. Since $R$ and $\Sigma$ are coprime, the class of $y_{t}(-1)^{t}$ modulo $\Sigma$ is also uniquely determined. By construction, however, the numbers $y_{i}(-1)^{i}$ are pairwise non-congruent modulo $\Sigma$, consequently, knowing the class of $y_{t}(-1)^{t}$, we can deduce $t$. Once $t$ is known, it is immediate to compute $u$ from the equation for $R'$ written above, then $\Delta$ from $R=(-1)^{t} \Delta$, and finally $d$.