MathDB
Guessing game with all but one of the numbers equal

Source: ITAMO 2016, Problem 6

May 11, 2016
combinatoricslinear combination

Problem Statement

A mysterious machine contains a secret combination of 20162016 integer numbers x1,x2,,x2016x_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 20162016 integer numbers y1,,y2016y_1,\ldots,y_{2016}, and the machine answers by telling the value of the sum x1y1++x2016y2016. 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.