A mysterious machine contains a secret combination of $2016$ integer numbers $x_1,x_2,\ldots,x_{2016}$. It is known that all the numbers in the combination are equal but one. One may ask questions to the machine by giving to it a sequence of $2016$ integer numbers $y_1,\ldots,y_{2016}$, and the machine answers by telling the value of the sum \[ x_1y_1+\dots+x_{2016}y_{2016}. \]After answering the first question, the machine accepts a second question and then a third one, and so on. Determine how many questions are necessary to determine the combination: (a) knowing that the number which is different from the others is equal to zero; (b) not knowing what the number different from the others is.
Problem
Source: ITAMO 2016, Problem 6
Tags: combinatorics, linear combination
laegolas
12.05.2016 02:45
Let the number that appears 2015 times in the combination be $x_s$, let the answer to a question $n$ be $A_n$, and let $x_d$ be the number that is different from the others. We can determine a combination iff we know $x_s$, $d$, and $x_d$.
It is given that $x_d=0$. We have $A_1=x_s\left( \sum_{i=1}^{2016} (y_i)-y_d \right)$. Given any sequence $y_i$, suppose the machine returns $A_1=\left( \sum_{i=1}^{2016} (y_i)-y_1 \right)\cdot \left( \sum_{i=1}^{2016} (y_i)-y_2 \right)$. There are two possibilities for $x_s$ and $d$:
$d=1$ and $x_s=\left( \sum_{i=1}^{2016} (y_i)-y_2 \right)$ or
$d=2$ and $x_s=\left( \sum_{i=1}^{2016} (y_i)-y_1 \right)$.
Thus, we need at least two questions to determine the combination. A possible two questions that satisfy are given below.
Question 1: Let $y_i=1$ for all $1\le i\le 2016$. It follows that $x_s=\frac{A_1}{2015}$.
Question 2: Let $y_i=2i-1$ for all $1\le i\le 2016$. It follows that $d=2016^2-A_2$.
Thus we can determine to combination with 2 questions.
dgrozev
14.05.2016 18:19
The answer to both a) and b) is the same: 2 questions. First, to show that one question is not enough, even for part a). It's enough to show that for any $y_1,y_2,\dots,y_n$, there exist two different $2016$-tuples: $(a_i)=(n,n,\dots,0,n,\dots,n)$ and $(b_i)=(m,m,\dots,0,m,\dots,m)$, such that: \[\sum y_i a_i = \sum y_i b_i.\]If there exist $y_i,y_j,y_i=y_j, i\neq j$, we can take $n=m=1$, but in one tuple $0$ is in the $i$-th place, in the other- in $j$-th place. In the case all $y_i$ are pairwise different, we can choose $n,m$ such that: \[n\sum_{i=1}^{2015} y_i= m\sum_{i=2}^{2016} y_i\]Thus, we checked the easier part. b) Two questions are enough. Let $n$ be the value of $2015$ members of $(x_i)$ and $n+m$ be the value of the different member, which is at the position $j$. We want to find $n,m,j$. The sum the machine would return is: \[S = n\cdot \sum_{i=1}^{2016} y_i + m\cdot y_j \]1-st question: $(y_i)=(1,-1,1,-1,\dots,1,-1)$. Since $\sum y_i=0$, after the machine's answer, we will find out the value of $|m|$, denote it with $m'$, that's we already know $m' = |m|$ 2-nd question. $(y_i)=(q-1, q+1,q+2,\dots, q+2015)$, where we chose $q$ such that $p:=\sum y_i$ is a prime number, greater than $2(m'+2016)$. It can be done applying Dirichlet's theorem. The machine's answer would be: \[S= np+(\pm 1)m' y_j\]It's easy to check that all members of the set: \[\big\{e\cdot m'y_i \mid e\in\{-1,1\}, i=1,2,\dots,2016\big\}\]have pairwise different residues modulo $p$. Since we know $S$ and $p$, we know what this residue should be. Hence, we can find the sign of $m$, that's $m$ itself, and $j$. After that, we find out $n$.