Question 133
Suppose $f : \{0,1\}^{10} \to \mathbb{R}$, i.e. $f(x_1, x_2, x_3, \dots, x_{10})$ is defined whenever $x_i \in \{0,1\}$ for each $1 \le i \le 10$. We are not given these values $f(x_1, \dots, x_{10})$, but, for every choice of $x_1, \dots, x_{10} \in \{0,1\}$, we know each of the following ten sums of two values of $f$:
$$
\begin{aligned}
f(0, x_2, x_3, \dots, x_{10}) &+ f(1, x_2, x_3, \dots, x_{10}) \\
f(x_1, 0, x_3, \dots, x_{10}) &+ f(x_1, 1, x_3, \dots, x_{10}) \\
f(x_1, x_2, 0, \dots, x_{10}) &+ f(x_1, x_2, 1, \dots, x_{10}) \\
& \qquad + \dots \\
f(x_1, x_2, \dots, x_9, 0) &+ f(x_1, x_2, \dots, x_9, 1)
\end{aligned}
$$
Show that knowing these sums does not allow us to compute the values of $f(x_1, \dots, x_{10})$.
Write down one or more other sums of values of $f$ at two distinct points such that if we know these sums as well as the above sums, then we can compute all values of $f$. You should justify your answer and use as few additional sums as possible.
$$
\begin{aligned}
f(0, x_2, x_3, \dots, x_{10}) &+ f(1, x_2, x_3, \dots, x_{10}) \\
f(x_1, 0, x_3, \dots, x_{10}) &+ f(x_1, 1, x_3, \dots, x_{10}) \\
f(x_1, x_2, 0, \dots, x_{10}) &+ f(x_1, x_2, 1, \dots, x_{10}) \\
& \qquad + \dots \\
f(x_1, x_2, \dots, x_9, 0) &+ f(x_1, x_2, \dots, x_9, 1)
\end{aligned}
$$
Show that knowing these sums does not allow us to compute the values of $f(x_1, \dots, x_{10})$.
Write down one or more other sums of values of $f$ at two distinct points such that if we know these sums as well as the above sums, then we can compute all values of $f$. You should justify your answer and use as few additional sums as possible.