IRL_ABooklet_2023

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{array}{rlrl}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{array}$$ 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$.