Let $A$ be the set of all binary sequences of length $n$ and denote $o =(0, 0, \ldots , 0) \in A$. Define the addition on $A$ as $(a_1, \ldots , a_n)+(b_1, \ldots , b_n) =(c_1, \ldots , c_n)$, where $c_i = 0$ when $a_i = b_i$ and $c_i = 1$ otherwise. Suppose that $f\colon A \to A$ is a function such that $f(0) = 0$, and for each $a, b \in A$, the sequences $f(a)$ and $f(b)$ differ in exactly as many places as $a$ and $b$ do. Prove that if $a$ , $b$, $c \in A$ satisfy $a+ b + c = 0$, then $f(a)+ f(b) + f(c) = 0$.
Problem
Source: Bulgaria MO 2000 Day 2 Problem 3
Tags: function, induction, vector, combinatorics proposed, combinatorics
04.02.2015 16:09
Rough sketch: note that $f$ preserves the number of $1$'s in a sequence, and show by induction on the number of $1$'s in the sequence the slightly stronger property that $f$ is actually a fixed permutation of the sequence.
04.02.2015 17:47
In other words, we have a function $f\colon \mathbb{F}_2^n \to \mathbb{F}_2^n$ with $f(0)=0$, and which preserves Hamming distances. We want to show that for $a+b+c=0$ we have $f(a)+f(b)+f(c) = 0$, thus $f(a+b) = f(c) = f(a)+f(b)$, which is equivalen to showing $f$ is linear. Notice that clearly $f$ must be injective (if $f(a)=f(b)$ then $a$ and $b$ differ in zero positions, so $a=b$), therefore $f$ is one-to-one. For any binary vector $v\in \mathbb{F}_2^n$ let us denote by $\emptyset \subseteq I(v)\subseteq \{1,2,\ldots,n\}$ the set of positions occupied by $1$'s. By the preserving of the Hamming distance, it follows that $|I(f(v))| = \operatorname{d}_{\textrm{Ham}}(f(v), 0) = \operatorname{d}_{\textrm{Ham}}(f(v), f(0)) = \operatorname{d}_{\textrm{Ham}}(v, 0)=|I(v)|$. Denote, as usual, $e_i = (0,\ldots,0,1,0,\ldots,0)$, with the $1$ on the $i$'th position. Then clearly (in the lights of the above) there exists a permutation $\sigma \in \mathcal{S}_n$ such that $f(e_i)=e_{\sigma(i)}$. Say $v\neq 0$; since $\displaystyle v = \sum_{i\in I(v)} e_i$, let us prove that $\displaystyle f(v) = f\left(\sum_{i\in I(v)} e_i\right ) = \sum_{i\in I(v)} e_{\sigma(i)} = \sum_{i\in I(v)} f(e_i)$. We have $\operatorname{d}_{\textrm{Ham}}(v, e_i) = |I(v)|-1$, therefore we also have $\operatorname{d}_{\textrm{Ham}}(f(v), f(e_i)) = \operatorname{d}_{\textrm{Ham}}(f(v), e_{\sigma(i)}) = |I(v)|-1$. This means $\sigma(i) \in I(f(v))$, and this for all $i\in I(v)$. Since $|I(v)| = |I(f(v))|$, it follows that $I(f(v)) = \{ \sigma(i) \mid i\in I(v)\}$, and so we proved our claim.