MathDB

3

Part of 2004 Iran MO (3rd Round)

Problems(1)

Beautiful

Source: Iran 2004

9/17/2004
Suppose V=Z2nV= \mathbb{Z}_2^n and for a vector x=(x1,..xn)x=(x_1,..x_n) in VV and permutation σ\sigma.We have xσ=(xσ(1),...,xσ(n))x_{\sigma}=(x_{\sigma(1)},...,x_{\sigma(n)}) Suppose n=4k+2,4k+3 n=4k+2,4k+3 and f:V→Vf:V \to V is injective and if xx and yy differ in more than n/2n/2 places then f(x)f(x) and f(y)f(y) differ in more than n/2n/2 places. Prove there exist permutaion σ\sigma and vector vv that f(x)=xσ+vf(x)=x_{\sigma}+v
vectorcombinatorics proposedcombinatorics