MathDB

Beautiful

Source: Iran 2004

September 17, 2004

vectorcombinatorics proposedcombinatorics

Problem Statement

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

\sigma

and

v

differ in more than

f(x)=x_{\sigma}+v

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

Back to Problems View on AoPS