Roots of unity problem

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

Roots of unity problem

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Polish MO 2019 P4

The post below has been deleted. Click to close.

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

1008 posts

#1 h May 19, 2019, 12:13 PM • 2 Y

Y by Adventure10, Mango247

Let $n,k,l$ be positive integers.Define injective function $f$ from $\{1,2,\dots,n\}$ to itself such that $f(i)-i\in \{k,-l\}$ .Prove that $k+l$ divides $n$ .

This post has been edited 1 time. Last edited by Ferid.---., May 19, 2019, 12:19 PM

Z K Y

The post below has been deleted. Click to close.

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

224 posts

#2 h May 19, 2019, 12:16 PM • 2 Y

Y by AlastorMoody, Adventure10

This problem was proposed by Burii.

Z K Y

The post below has been deleted. Click to close.

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

1000 posts

#3 h May 19, 2019, 12:26 PM • 7 Y

Y by Pluto1708, Semcio, Mprog., Adventure10, Mango247, Mango247, ismayilzadei1387

Let $\omega = e^{\frac{2\pi i}{k+l}}$
Then by the given condition $\{\omega^1,\omega^2,\dots,\omega^n\}=\{\omega^{1+k},\omega^{2+k},\dots,\omega^{n+k}\}$ .Looking at sum we get that either $\omega^n$ or $\omega^k$ equals $1$ or $k+l$ divides either $n$ or $k$ .Since $l>0$ we get that $k+l$ divides $n$ .

This post has been edited 1 time. Last edited by tenplusten, May 19, 2019, 12:27 PM

Z K Y

The post below has been deleted. Click to close.

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

9022 posts

#4 h May 20, 2019, 7:57 AM • 4 Y

Y by AlastorMoody, pieater314159, Adventure10, Mango247

Thank you for posting this problem. However, it would be nice to not put the most important hint for this problem already in the title.
This would give users in this forum the chance to think about the problem in an unbiased way. Thanks!

Z K Y

The post below has been deleted. Click to close.

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

281 posts

#5 h May 21, 2019, 1:09 PM • 2 Y

Y by Adventure10, Mango247

Non-complex solution

Z K Y

The post below has been deleted. Click to close.

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

252 posts

#6 h May 22, 2019, 8:59 AM • 4 Y

Y by ayamgabut, Mprog., Adventure10, Stuffybear

similar as above

Z K Y

The post below has been deleted. Click to close.

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

39 posts

Mprog.

#7 h Jul 16, 2019, 3:21 PM • 2 Y

Y by Adventure10, Mango247

tenplusten wrote:

Let $\omega = e^{\frac{2\pi i}{k+l}}$
Then by the given condition $\{\omega^1,\omega^2,\dots,\omega^n\}=\{\omega^{1+k},\omega^{2+k},\dots,\omega^{n+k}\}$ .Looking at sum we get that either $\omega^n$ or $\omega^k$ equals $1$ or $k+l$ divides either $n$ or $k$ .Since $l>0$ we get that $k+l$ divides $n$ .

What should I study to fully understand this solution?

Z K Y

The post below has been deleted. Click to close.

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

1107 posts

#8 h Jul 16, 2019, 5:43 PM • 2 Y

Y by mueller.25, Adventure10

Mprog. wrote:

tenplusten wrote:

Let $\omega = e^{\frac{2\pi i}{k+l}}$
Then by the given condition $\{\omega^1,\omega^2,\dots,\omega^n\}=\{\omega^{1+k},\omega^{2+k},\dots,\omega^{n+k}\}$ .Looking at sum we get that either $\omega^n$ or $\omega^k$ equals $1$ or $k+l$ divides either $n$ or $k$ .Since $l>0$ we get that $k+l$ divides $n$ .

What should I study to fully understand this solution?

I too had doubt understanding it until I asked him his reply was that $\omega^{f (i)}=\omega^{i+k}$ or $\omega^{i-l}$
and since $\omega^{k+l}=1$ we have $\omega^{i+k}=\omega^{i-l}$ $\implies$ $\omega^{f (i)}=\omega^{i+k}$
This shows that since both sets are the same so they must have the same sum then take common and using the fact that $1+\omega+\cdots \omega^{n-1}=\dfrac{\omega^{n}-1}{\omega-1}$ conclude that either $\omega^n$ or $\omega^k$ equals $1$ .But since $\omega^{k+l}=1$ so his solution follows

This post has been edited 1 time. Last edited by Pluto1708, Jul 16, 2019, 5:43 PM

Z K Y

The post below has been deleted. Click to close.

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

39 posts

Mprog.

#9 h Jul 17, 2019, 12:09 PM • 2 Y

Y by Adventure10, Mango247

Thank you very much sir

Z K Y

The post below has been deleted. Click to close.

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

62 posts

#10 h Mar 30, 2024, 6:25 PM

Y by

I will change the notation from $\sigma$ to $f$ . If $f \ : \ [n] \rightarrow [n]$ is an injection and the domain and codomain are the same cardinality, then it means that is it a bijection. Also, let $g=f^{-1}$ .

For $i=1,...,l$ we have $f(i)=i+k$ .
Proof: $f(i)-i>0-i \leq -l$ , so it must be $f(i)-i=k$ .
For $i=1,...,k$ we have $g(i)=i+l$ .
Proof: $i-g(i)<i<k$ , so it must be $i-g(i)=-l$ .

It means that $f(i)=i+k$ for $i=1,...,l$ and $f(i)=i-l$ for $i=l+1,...,l+k$ .

Now let $s=k+l$ .

For $i=s+1,...,s+l$ we have $f(i)=i+k$
Proof: Suppose we had $f(i)-i=-l$ , then $f(i)=i-l \leq s$ which is impossible because every number from $1,...s$ is already a value of $f$ for one of the numbers $1,...,s$ . Contradiction.
For $i=s+1,...,s+k$ we have $g(i)=i+l$
Proof: Suppose we had $i-g(i)=k$ , then $g(i)=i-k \leq s$ , but for all numbers $1,...,s$ function $f$ takes a value that is no more than $s$ . Contradiction.

It means that $f(i)=i+k$ for $i=s+1,...,s+l$ and $f(i)=i-l$ for $i=s+l+1,...,2s$ .

Now, let $n=s \cdot q +r$ , where $q \in \mathbb{N}$ and $r \in \left \lbrace 0,...,s \right \rbrace$ . Repeating the argument above, we can state that:
$f(i)=i+k, \quad i=1,...,l, \quad s+1,...,s+l, \quad ..., \quad (q-1)s+1,...,(q-1)s+l$ $f(i)=i-l, \quad i=l+1,...,s, \quad s+l+1,...,2s, \quad ..., \quad (q-1)s+l,...,qs$
Suppose that $r \in \left \lbrace 1,...,l \right \rbrace$ . Then we can't have $f(sq+r)-(sq+r)=k$ as then we would have $f(sq+r)=sq+r+k>n$ . So we must have $f(sq+r)-(sq+r)=-l$ and so $f(sq+r)=sq+r-k \leq sq$ which is impossible because $sq$ is value of $f$ for one of the numbers $1,...,sq$ . Contradiction.

Suppose that $r \in \left \lbrace l+1,...,s-1 \right \rbrace$ . Then we can't have $sq+r-l+1-g(sq+r-l+1)=-l$ as then we would have $g(sq+r-l+1)=sq+r+1>n$ . So we must have $sq+r-l+1-g(sq+r-l+1)=k$ and so $g(sq+r-l+1)=sq+r-l-k+1 \leq sq$ which is impossible because every number from $1,...,sq$ is value of $f$ for one of the numbers $1,...,sq$ . Contradiction.

Z K Y

The post below has been deleted. Click to close.

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

19 posts

Avron

#11 h Yesterday at 1:21 PM

Y by

We prove by induction that $f(m(k+l)+r)=m(k+l)+r+k$ for all $1<r<l+1$ by induction on $m$ . For $m=0$ it's obvious as $r-l\leq 0$ . Now assume that $f((m+1)(k+l)+r)=(m+1)(k+l)+r-l=m(k+l)+r+k=f(m(k+l)+r)$ which is a contradiction. Now let $n=m(k+l)+r$ , where $0\leq r <l+k$ . If $r\neq 0$ then $f(m(k+l)+\min(r,l))=m(k+l)+\min(r,l)+k>n$ , so we're done.

This post has been edited 1 time. Last edited by Avron, Yesterday at 1:22 PM
Reason: mispell

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a