The Appetizer of Iran NT2023

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

The Appetizer of Iran NT2023

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Iran MO 3rd round 2023 NT exam , P1

The post below has been deleted. Click to close.

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

168 posts

#1 h Aug 17, 2023, 4:09 PM

Y by

Find all integers $n > 4$ st for every two subsets $A,B$ of $\{0,1,....,n-1\}$ , there exists a polynomial $f$ with integer coefficients st either $f(A) = B$ or $f(B) = A$ where the equations are considered mod n.
We say two subsets are equal mod n if they produce the same set of reminders mod n. and the set $f(X)$ is the set of reminders of $f(x)$ where $x \in X$ mod n.

This post has been edited 1 time. Last edited by alinazarboland, Sep 13, 2023, 8:51 AM

Z K Y

The post below has been deleted. Click to close.

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

Shayan-TayefehIR

104 posts

Shayan-TayefehIR

#2 h Aug 17, 2023, 7:37 PM • 2 Y

Y by BADIHI, David-Vieta

We'll show that the answer is all prime numbers $p$ .

Case 1: There exist coprime natural numbers $x , y > 1$ such that $n=xy$ .
Define sets $A$ and $B$ as $A=\{0,1,...,xy-1\}$ and $B=\{x,y\}$ . While $|A|>|B|$ , then it's enough to show that there doesn't exist a polynomial $f \in \mathbb{Z}[x]$ such that $f(A) \equiv B \pmod n$ .
Considering the counterexample , there exist natural numbers $i , j \in \mathbb{N}$ such that $f(i) \equiv x \pmod y$ and $f(j) \equiv y \pmod x$ ; thus since $gcd(x , y)=1$ , by CRT there exist a natural number $a$ such that :
$f(a) \equiv x \pmod y$ $f(a) \equiv y \pmod x$ And while $f(a)$ equals to $x$ or $y$ modulo $xy$ , we can get that $x|y$ or $y|x$ which is a contradiction.

Case 2: There exist an odd prime number $p$ such that $n=p^2$ .
Define $A=\{0,1,...,p^2-1\}$ and $B=\{1,2,...,p,p+1\}$ . Then if there exist a proper polynomial $f(x)$ , since this polynomial produce a complete residue system modulo $p$ , there exist a unique number $i \in \mathbb{N}$ such that $f(i) \equiv 1 \pmod p$ and for each natural number $k$ we have :
$f(i+pk) \equiv f(i)+pkf'(i) \pmod {p^2}$ and if $p|f'(i)$ , all of the $f(i+pk)$ values are $1$ modulo $p^2$ and they don't produce $p+1$ .
Also if $gcd(p , f'(i))=1$ , values of $f(i+pk)$ produce all numbers $1 , p+1 , 2p+1 , ... , (p-1)p+1$ modulo $p^2$ which is a contradiction again. Obviously by considering same sets for each $n=p^k$ , we can get the contradiction too.

Case 3: $n=8$ .
Define $A=\{0,1,4,5\}$ and $B=\{0,1,2\}$ . Thus if $f(A) \equiv B \pmod 8$ , without losing the generality we can assume that $f(0)$ and $f(4)$ are even and while these numbers are equal modulo $4$ , they can't be $0 , 2$ modulo $8$ which is a contradiction.Obviously by considering same sets for each $n=2^k > 4$ , we can get the contradiction too.

Case 4: $n$ equals to a prime number $p$ .
Since for arbitrary natural numbers $a_1 , ... , a_p$ , by Lagrange interpolation there exist a polynomial $f(x)$ with integer coefficients such that $f(i) \equiv a_i \pmod p$ for each $i$ , these numbers are suitable. So we're done.

This post has been edited 7 times. Last edited by Shayan-TayefehIR, Aug 17, 2023, 9:00 PM

Z K Y

The post below has been deleted. Click to close.

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

5 posts

BADIHI

#3 h Aug 18, 2023, 8:40 AM • 1 Y

Y by Shayan-TayefehIR

Another solution for composite numbers
set $N = ab$ when $a$ and $b$ both greater than $1$ .

$X =\{ 1 , 2 , .... , a-1 , a+1 , ..... , 2a - 1 , 2a +1 , ........., ab - 1\}$
$Y = \{ 0 , 1 , 2 , ..... , a-1\}$
It's easy to check this two sets works though the $f(X)$ can't produce all the remainders of $a$ .

Z K Y

The post below has been deleted. Click to close.

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

46 posts

#4 h Sep 7, 2023, 2:51 AM

Y by

Shayan-TayefehIR wrote:

We'll show that the answer is all prime numbers $p$ .

Case 1: There exist coprime natural numbers $x , y > 1$ such that $n=xy$ .
Define sets $A$ and $B$ as $A=\{0,1,...,xy-1\}$ and $B=\{x,y\}$ . While $|A|>|B|$ , then it's enough to show that there doesn't exist a polynomial $f \in \mathbb{Z}[x]$ such that $f(A) \equiv B \pmod n$ .
Considering the counterexample , there exist natural numbers $i , j \in \mathbb{N}$ such that $f(i) \equiv x \pmod y$ and $f(j) \equiv y \pmod x$ ; thus since $gcd(x , y)=1$ , by CRT there exist a natural number $a$ such that :
$f(a) \equiv x \pmod y$ $f(a) \equiv y \pmod x$ And while $f(a)$ equals to $x$ or $y$ modulo $xy$ , we can get that $x|y$ or $y|x$ which is a contradiction.

Case 2: There exist an odd prime number $p$ such that $n=p^2$ .
Define $A=\{0,1,...,p^2-1\}$ and $B=\{1,2,...,p,p+1\}$ . Then if there exist a proper polynomial $f(x)$ , since this polynomial produce a complete residue system modulo $p$ , there exist a unique number $i \in \mathbb{N}$ such that $f(i) \equiv 1 \pmod p$ and for each natural number $k$ we have :
$f(i+pk) \equiv f(i)+pkf'(i) \pmod {p^2}$ and if $p|f'(i)$ , all of the $f(i+pk)$ values are $1$ modulo $p^2$ and they don't produce $p+1$ .
Also if $gcd(p , f'(i))=1$ , values of $f(i+pk)$ produce all numbers $1 , p+1 , 2p+1 , ... , (p-1)p+1$ modulo $p^2$ which is a contradiction again. Obviously by considering same sets for each $n=p^k$ , we can get the contradiction too.

Case 3: $n=8$ .
Define $A=\{0,1,4,5\}$ and $B=\{0,1,2\}$ . Thus if $f(A) \equiv B \pmod 8$ , without losing the generality we can assume that $f(0)$ and $f(4)$ are even and while these numbers are equal modulo $4$ , they can't be $0 , 2$ modulo $8$ which is a contradiction.Obviously by considering same sets for each $n=2^k > 4$ , we can get the contradiction too.

Case 4: $n$ equals to a prime number $p$ .
Since for arbitrary natural numbers $a_1 , ... , a_p$ , by Lagrange interpolation there exist a polynomial $f(x)$ with integer coefficients such that $f(i) \equiv a_i \pmod p$ for each $i$ , these numbers are suitable. So we're done.

But how about $n=4$ ? I wrote a program and see that there exists $f$ with its degree $\leq 3$ that satisfy the condition for every $A,B$ . However, how can we prove it mathematically?

This post has been edited 2 times. Last edited by Anan_PZ, Sep 7, 2023, 2:55 AM
Reason: Typo

Z K Y

The post below has been deleted. Click to close.

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

46 posts

#5 h Sep 7, 2023, 9:46 AM

Y by

It is not hard to show that $n=4$ is also a solution.
Two facts:
1. If $f(A) = B$ , then for $\tilde{A} = A+a, \tilde{B} = B+b$ , let $\tilde{f}(x) = f(x-a)+b$ , we'll have $\tilde{f}(\tilde{A}) = \tilde{B}$ .
2. If $f_1(A)=B, f_2(B)=C$ , then let $f_3(x) = f_2(f_1(x))$ , we'll have $f_3(A)=C$ .

Based on these facts, it's sufficient to consider the following five subsets of $\{0,1,2,3\}$ : $\{0\},\{0,2\},\{0,1\},\{0,1,2\},\{0,1,2,3\}$ .
1) $A=\{0,2\}, B=\{0\}$ , $f(x) = 0$ .
2) $A=\{0,1\}, B=\{0,2\}$ , $f(x) = 2x$ .
3) $A=\{0,1,2\}, B=\{0,1\}$ , $f(x) = x^2$ .
4) $A=\{0,1,2,3\}, B=\{0,1,2\}$ , $f(x) = x^3+1$ .
Therefore, the proposition is true for $n=4$ as well.

Z K Y

The post below has been deleted. Click to close.

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

Shayan-TayefehIR

104 posts

Shayan-TayefehIR

#6 h Sep 12, 2023, 11:16 AM

Y by

Anan_PZ wrote:

It is not hard to show that $n=4$ is also a solution.
Two facts:
1. If $f(A) = B$ , then for $\tilde{A} = A+a, \tilde{B} = B+b$ , let $\tilde{f}(x) = f(x-a)+b$ , we'll have $\tilde{f}(\tilde{A}) = \tilde{B}$ .
2. If $f_1(A)=B, f_2(B)=C$ , then let $f_3(x) = f_2(f_1(x))$ , we'll have $f_3(A)=C$ .

Based on these facts, it's sufficient to consider the following five subsets of $\{0,1,2,3\}$ : $\{0\},\{0,2\},\{0,1\},\{0,1,2\},\{0,1,2,3\}$ .
1) $A=\{0,2\}, B=\{0\}$ , $f(x) = 0$ .
2) $A=\{0,1\}, B=\{0,2\}$ , $f(x) = 2x$ .
3) $A=\{0,1,2\}, B=\{0,1\}$ , $f(x) = x^2$ .
4) $A=\{0,1,2,3\}, B=\{0,1,2\}$ , $f(x) = x^3+1$ .
Therefore, the proposition is true for $n=4$ as well.

Thank you for mentioning that , actually the problem says to find all proper number $n>4$ on the exam. ( Surely for avoiding this messy case. )

Z K Y

The post below has been deleted. Click to close.

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

10 posts

A22-

#7 h Apr 30, 2025, 9:36 AM

Y by

The construction part is not so hard, so we just prove that >4 composites dont work.
If n>4 is a composite then we can write n=ab st b>2 and a>1.
Let A={a,2a,3a} and B={0,1}. Then f(A)=B (mod n)
Wlog assume f(a) = 0 and f(2a) = 1 (mod n)
We have a | n , so we have f(a)=f(2a)=0=1 (mod a)
Thus a=1 , a contradiction.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a