Suppose $V= \mathbb{Z}_2^n$ and for a vector $x=(x_1,..x_n)$ in $V$ and permutation $\sigma$.We have $x_{\sigma}=(x_{\sigma(1)},...,x_{\sigma(n)})$ Suppose $ n=4k+2,4k+3$ and $f:V \to V$ is injective and if $x$ and $y$ differ in more than $n/2$ places then $f(x)$ and $f(y)$ differ in more than $n/2$ places. Prove there exist permutaion $\sigma$ and vector $v$ that $f(x)=x_{\sigma}+v$
Problem
Source: Iran 2004
Tags: vector, combinatorics proposed, combinatorics
23.09.2004 20:49
First you should write the other two parts of the question! 1) If $D(x,y)$ be the number of differences between $x$ and $y\in V$ then the number of $z\in V$ such that $D(z,x)>{n\over 2}$ and $D(z,y)>{n\over 2}$ only depends on $D(x,y)$. Proof is easy!Only you should change the members of vectors. 2) Suppose the number of shuch $z$'s in (1) is $l_k$.($k=D(x,y)$) Then $l_1 =l_2 >l_3 =l_4 >l_5 =l_6>\ldots$ Proof of this one is also easy.By only transforming each $z$ into another $z$! Now that we know these we come to prove the main problem. Because $n=4k+2$ or $n=4k+3$ , $[{n\over 2}]=2k+1$ so $[{n\over 2}]+1=2k$. Now suppose that $D(x,y)=k$. The number of $z$'s that are good (like the part 2) to $x$ and $y$ are $l_k$. Suppose $D(f(x),f(y))=r$. We have that $f(z)$ is also good to $f(x)$ and $f(y)$ and also the inverse. By part 2 we have $|r-k|<2$. Now suppose that $D(x,y)=[{n\over 2}]+1$. Because it's an even number then $D(f(x),f(y))=[{n\over 2}]$ or $[{n\over 2}]+1$. But its more than $n\over 2$. So it is exactly $[{n\over 2}]+1$. So $D(f(x),f(y))=D(x,y)$ By the same proof we have if $D(x,y)=[{n\over 2}]$ then $D(x,y)=D(f(x),f(y))$. Now suppouse $x\in V$ and $i\in \{1,\ldots,n\}$.There exist a $y\in V$ such that $D(x,y)=[{n\over2}]+1$ and and differs with $x$ in the $i$'th member. Also there exist a $y'$ such that it only differs with $y$ in $i$'th member. We have $D(x,y)=D(f(x),f(y))$ and $D(x,y')=D(f(x),f(y'))$. Now suppose that $I$ is the set of indexes that $f(x)$ and $f(y)$ differ in. Construct $I'$ like the $I$ for $f(x)$ and $f(y')$. We want to prove that $I'\subset I$. If it is not then it is easily seen that $I$ and $I'$ differ in more than 2 members. But $D(y,y')=1$ so $D(f(y),f(y'))<3$. So $I\subset I'$. By changing $x$ we can make the $y$ to become all the members of $V$. So for every $y\in V$ changing one member causes one change to $f(y)$. Suppose that $x\in V$. And suppose that changing the $i$'th member causes the $g(i)$'th member of $f(x)$ to change. We have $g$ is a permutation because $f$ is injective. We shall now prove that $g$ is uniqe for all $x\in V$. Suppose that it is not. So we have $x,y\in V$ and $i\in \{1,\ldots,n\}$ such that a change to $x$ in $i$ causes the $j$'th member of $f(x)$ to change, and a change to $y$ causes the $k$'th member. Suppose that the changed $x$ is $x'$ and the changed $y$ is $y'$. $D(x,y)=D(x',y')=t$ $|D(f(x'),f(y'))-t|<2$ But |D(f(x'),f(y'))-t| is even because we have two changes in $f(x)$ and $f(y)$ to obtain $f(x')$ and $f(y')$. So $D(f(x'),f(y'))=t$ So $D(f(x'),f(y))-D(f(x),f(y))=1$ xor $D(f(x),f(y'))-D(f(x),f(y))=1$ and the other one is $-1$. Suppose the first one is $-1$. Then it is easily seen that $D(f(x),f(y))-D(x,y)=1$.(Because in other ways we have $|D(f(x'),f(y))-D(x',y)|>1$) But from the $D(f(x),f(y'))-D(f(x),f(y))=1$ we get $D(x,y)=D(f(x),f(y))$.(Like the last part) So $g$ is uniqe for all $x\in V$. Now because that we can change every $x$ to every $y$ by changing members, we have that the problem is proved!
28.09.2004 11:14
Of course Nima you got the best mark from this question.Well done.