APMO 2019 P1 Doppelganger?

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

APMO 2019 P1 Doppelganger?

G H J

Reveal topic tags

functional equation

L

G H BBookmark kLocked kLocked NReply

Source: DeuX Mathematics Olympiad 2021 Shortlist N4 (Problem 5)

The post below has been deleted. Click to close.

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

1063 posts

#1 h Sep 7, 2021, 5:17 PM • 1 Y

Y by centslordm

Determine all eventually surjective functions $f: \mathbb{N} \to \mathbb{N}$ such that
$f(f(a)) + b | a^2 + f(a)f(b)$ holds for all $a,b \in \mathbb{N}$ .

A function $f: \mathbb{N} \to \mathbb{N}$ is $\textit{eventually surjective}$ if and only if there exists $N \in \mathbb{N}$ so that for every $n \geq N$ , there exists $m \in \mathbb{N}$ such that $f(m) = n$ .

Proposed by Stanve Avrilium, Indonesia

Remark

This post has been edited 1 time. Last edited by GorgonMathDota, Sep 7, 2021, 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.

1079 posts

#3 h Sep 7, 2021, 5:42 PM • 1 Y

Y by centslordm

I think that the surjectivity condition is unnecessary.

Let $P(a,b)$ denote the assertion of given.
Then, $P(a,nf(a)-f(f(a)))\implies na\mid a^2+f(a)f(nf(a)-f(f(a))),$ where $n$ is chosen large enough in order to make $nf(a)>f(f(a))$ . Thus, $f(a)\mid a^2$ .
Take $a=p\in\mathbb{P}$ , thus either $f(p)=1,p$ or $p^2$ for all primes $p$ .
Claim. $f$ is injective.
Proof. Take $x,y$ with $f(x)=f(y)$ . Now, $P(x,b)$ and $P(y,b)$ together imply $f(f(x))+b\mid x^2-y^2$ . Taking $b\to\infty$ , we obtain that $x=y$ , the claim follows. $\square$

Hence as $f$ is injective, we get that only one prime can take the value $1$ , meaning either $f(p)=p$ or $f(p)=p^2$ for infinitely many primes.

Suppose we have infinitely many primes $p$ such that $f(p)=p^2$ .
Take one prime $q$ with $f(q)=q^2$ , thus
$P(q,x-f(q^2))\implies x\mid q^2(1+f(x-f(q^2))).$ Note that $f(q^2)\mid q^4$ , hence either $f(q^2)=q,q^3,q^4$ due to injectivity. Note that the last two are also impossible as then taking $x=q^5+q^4$ or $x=q^5+q^3$ , we obtain that $q\mid 1+f(q^5)$ , which is impossible as $q\mid f(q^5)$ .

Hence we now consider $f(q)=q^2$ and $f(q^2)=q$ . Indeed, $P(q,b)\implies q+b\mid q^2(1+f(b))$ and taking $b\perp q$ and $q\to \infty$ , we obtain that $f(b)=-1$ , impossible. We conclude that $f(p)=p$ for infinitely many primes $p$ .

Hence, $P(p,b)\implies p+b\mid p(p+f(b))$ , taking $b<p\in\mathbb{P}$ and $p$ sufficiently large, we get $p+b\mid p+f(b)\implies p+b\mid f(b)-b$ and hence we get that $f(b)=b$ for all $b$ . Our only solution is the identity function, $\boxed{f(x)=x\forall x\in\mathbb{N}}$ .

Z K Y

The post below has been deleted. Click to close.

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

1301 posts

#4 h Sep 7, 2021, 11:59 PM • 1 Y

Y by k12byda5h

The answer is $f(x)\equiv x$ . Here is a solution without the surjectivity condition.

Let $P(x,y)$ denote the assertion that $f(f(x))+y\mid x^2+f(x)f(y)$ .

Claim: $f(x)\mid x^2$

Proof: Pick $y$ such that $f(f(x))+y$ is divisible by $f(x)$ . Thus, $f(x)|f(f(x))+y\mid x^2+f(x)f(y)$ , so $f(x)\mid x^2$ .

This implies $f(1)=1$ and for all primes $p$ , $f(p)\in \{1,p,p^2\}$ .

$P(1,p)$ gives $1+p\mid 1+f(p)$ , so $f(p)=p$ for all primes $p$ .

Finally, suppose $f(y)-y\ne 0$ . Let $d=|f(y)-y|$ and let $p$ be a prime greater than $d$ and $y$ . Then $P(p,y)$ gives $p+y\mid p^2+pf(y)$ . Since $p>y, \gcd(p,p+y)=1$ , so $p+y\mid p+f(y)$ , so $p+y\mid |f(y)-y|$ . However, $0<|f(y)-y|<p+y$ , contradiction!

Therefore, $f(x)\equiv x$

Z K Y

The post below has been deleted. Click to close.

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

1069 posts

gghx

#5 h Sep 8, 2021, 7:43 AM • 1 Y

Y by Mango247

Here i think is a sketch of a solution with the surjective condition.

Get $f(1)=1$ as above.
$P(1,b): 1+b|1+f(b)$ . Taking $f(b)+1$ prime this means $f(b)=b$ for infinitely many $b$ .
Now $P(a,b)$ where $f(a)=a$ gives $a+b|b^2-bf(b)$ so $f(b)=b$ for all $b$ .
Please correct me if there is a mistake.

This post has been edited 2 times. Last edited by gghx, Sep 8, 2021, 7:45 AM

Z K Y

The post below has been deleted. Click to close.

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

awesomeming327.

1682 posts

awesomeming327.

#6 h Mar 29, 2025, 3:05 AM

Y by

Claim 1: $f(a)\mid a^2$

Let $b=nf(a)-f(f(a))$ for large enough $n$ . The left hand side is $nf(a)$ while the right hand side is $a^2+f(a)f(b)$ so $f(a)\mid a^2$ as desired.

This gives $f(1)=1$ , so letting $a=1$ we get $1+b\mid 1+f(b)$ so $f(b)\ge b$ . If $b$ is prime then $f(b)=b$ . Now take $a$ prime which gives $a+b\mid a^2+af(b)\implies a+b\mid b^2-bf(b)$ . Setting $a$ to be large, $f(b)=b$ for all $b$ .

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a