Competition problem — Algebra — Maths Olympiad Prep

Library / /32 of 42

Algebra Difficulty 6.7 National olympiad Prove it Ireland

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.

Solution

We consider the natural generalisation with $10$ replaced everywhere by $n$ for some $n > 1$ , $n \in \mathbb{N}$ . It is convenient to use vector notation, writing $f(\underline{x})$ in place of $f(x_1, \dots, x_n)$ . To show that the given sums are insufficient to compute all $f$ -values, it suffices to note that if we write $s(\underline{x}) = \sum_{i=1}^n x_i$ and then redefine $f$ by adding $(-1)^{s(\underline{x})}$ to $f(\underline{x})$ , then all the listed sums remain the same.
We will prove that, the value of the additional sum
$f(0, 0, 0, 0, \dots, 0) + f(1, 1, 0, 0, \dots, 0)$
suffices to compute the values of $f$ .
It can be shown in a similar way that any other additional sum of the form $f(\underline{a}) + f(\underline{b})$ , for some fixed $\underline{a}, \underline{b}$ , where $s(\underline{a})$ and $s(\underline{b})$ have the same parity, or equivalently where $\underline{a}$ and $\underline{b}$ differ in an even number of positions, is sufficient.

Solution 1. We know all sums of the form $S := f(\underline{x}) + f(\underline{y})$ for vectors $\underline{x}, \underline{y}$ that differ in a single position. We also know $T := f(\underline{y}) + f(\underline{z})$ , whenever $\underline{y}$ and $\underline{z}$ differ in a single position, and so we know $S - T = f(\underline{x}) - f(\underline{z})$ . Thus, we know such differences whenever $\underline{x}$ and $\underline{z}$ differ in exactly two positions. By repeating the process of taking differences, we can compute $f(\underline{u}) - f(\underline{v})$ whenever $\underline{u}$ and $\underline{v}$ differ in any even number of positions. In particular, we can compute $f(\underline{a}) - f(\underline{b})$ where $\underline{a} = (0, 0, 0, 0, \dots, 0)$ and $\underline{b} = (1, 1, 0, 0, \dots, 0)$ . Since we also know $f(\underline{a}) + f(\underline{b})$ , we can compute $f(\underline{a})$ .
Knowing $f(\underline{a})$ allows us to compute all values. In fact, if $\underline{u}$ differs from $\underline{a}$ in exactly one position, then knowing $f(\underline{a}) + f(\underline{u})$ allows us to compute $f(\underline{u})$ . Applying the same argument to $f(\underline{u})$ , we compute $f(\underline{v})$ whenever $\underline{v}$ differs from $\underline{u}$ in exactly one position, and so whenever $\underline{v}$ differs from $\underline{a}$ in exactly two positions. Iterating this approach, we get all other values of $f$ .

Solution 2. We prove our claim by induction on the dimension $n > 1$ . Suppose first that $n = 2$ , so we know
$\begin{aligned} A &:= f(0, 0) + f(1, 0), & B &:= f(1, 1) + f(0, 1), \\ C &:= f(0, 0) + f(0, 1), & D &:= f(1, 1) + f(1, 0). \end{aligned}$
The additional sum is $E = f(0, 0) + f(1, 1)$ . Since $A - D = f(0, 0) - f(1, 1)$ , knowing $E$ allows us to compute
$f(0, 0) = (E + A - D)/2,$
and using $A, C, E$ we find the remaining three values of $f$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.