Beautiful

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Beautiful

G H J

Reveal topic tags

combinatorics proposed

L

G H BBookmark kLocked kLocked NReply

Source: Iran 2004

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1275 posts

#1 h Sep 17, 2004, 7:16 AM • 2 Y

Y by Adventure10, Mango247

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Nima Ahmadi Pour

160 posts

Nima Ahmadi Pour

#2 h Sep 23, 2004, 5:49 PM • 2 Y

Y by Adventure10, Mango247

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!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1275 posts

#3 h Sep 28, 2004, 8:14 AM • 2 Y

Y by Adventure10, Mango247

Of course Nima you got the best mark from this question.Well done.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a