Tricky, tricky

Probability Level 5

In a certain game, the first player secretly chooses an $2015-$ dimensional vector $a = (a_1, a_2, . . . , a_{2015})$ all of whose components are integers.

The second player is to determine $a$ by choosing any $2015-$ dimensional vectors $x_i$ , all of whose components are also integers.

For each $x_i$ chosen, and before the next $x_i$ is chosen, the first player tells the second player the value of the dot product $x_i \cdot a$ .

What is the least number of vectors $x_i$ the second player has to choose in order to be able to determine $a$ ?

The answer is 2.

1 solution

Khang Nguyen Thanh
Oct 9, 2015

Two $x_i$ are sufficient.

Pick $x_1 = a$ and you learn what $a \cdot a$ is.

Then pick $x_2 = (1, M, M^2, M^3, \ldots, M^{2015})$ where $M > 2\sqrt{a \cdot a} = 2Q$ .

Then $a \cdot x_2 = a_1 + a_2M + \ldots + a_{2015}M^{2015}$ .

The $a_i$ can be determined by constructing

$N = a \cdot x_2 + Q(1 + M + \ldots + M^{2015})= (a_1 + Q) + (a_2 + Q)M + · · · + (a_{2015} + Q)M^{2015}$ .

Writing $N$ in base $M$ produces the $i-$ th digit $a_i + Q$ from which we subtract $Q$ to get $a_i$ .

But if we knew a, we wouldn't be guessing. You need 2015, because you're solving a system of equations in 2015 variables. (Or you would, if you didn't think to use the obvious strategy of guessing the columns of I_2015)

Justin Eberlein - 5 years, 8 months ago

How can you pick $x_1 = a$ if you don't know $a$ ?

Ivan Koswara - 5 years, 8 months ago

Tricky, tricky

The answer is 2.

1 solution

0 pending reports