Serbian selection contest for the BMO 2025 - P2

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

Serbian selection contest for the BMO 2025 - P2

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

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

39 posts

#1 h Apr 7, 2025, 10:12 PM

Y by

Find all functions $f : \mathbb{N} \to \mathbb{N}$ such that $f(a) + f(b) \mid af(a) - bf(b)$ , for all $a, b \in \mathbb{N}$ .
(Here, $\mathbb{N}$ is a set of positive integers.)

Proposed by Vukašin Pantelić

Z K Y

The post below has been deleted. Click to close.

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

1412 posts

#2 h Apr 7, 2025, 11:41 PM

Y by

Very nice one. I claim $f(n)$ is of the following form: for arbitrary $c\in\mathbb{N}$ , $f(n)=cn$ for all $n$ , which clearly works.

Denote the given assertion by $P(a,b)$ . Note that $P(a,b)$ gives $f(a)+f(b)\mid af(a)-bf(b)$ , so $f(a)+f(b)\mid (a+b)f(b)$ . Taking $a=p-1$ and $b=1$ , we find $f(p-1)+f(1)\mid pf(1)$ . Set $f(1)=c$ to obtain $f(p-1)+c\mid pc$ . Note that there is a divisor $d\mid c$ and an infinite set $S$ of primes for which $f(p-1)+c = pd$ for every $p\in S$ . Take $c=du$ to write $f(p-1) = d(p-u)$ . Our goal is to verify that $u=1$ .

We next inspect $P(p-1,q-1)$ for $p,q\in S$ . We have $f(p-1)+f(q-1) = d(p+q-2u)$ . Furthermore,
$(p-1)f(p-1) - (q-1)f(q-1) = d((p-1)(p-u)-(q-1)(q-u)) = d(p-q)(p+q-u-1).$ So,
$f(p-1)+f(q-1)\mid (p-1)f(p-1) - (q-1)f(q-1)\Leftrightarrow p+q-2u\mid (p-q)(p+q-u-1).$ Notice now that $p+q\equiv 2u\pmod{p+q-2u}$ . So, $p+q-u-1\equiv u-1\pmod{p+q-2u}$ . Furthermore, $q\equiv -p+2u\pmod{p+2u-q}$ , so
$(p-q)(p+q-u-1)\equiv (u-1)2(p-u).$ We can clearly assume $q>p>u$ . Fixing $p,q$ , we see that $|(p-q)(p+q-u-1)|$ is unbounded as $q\to\infty$ , which is a contradiction unless $u=1$ . So, $f(p-1)=d(p-1)$ for all $p\in S$ .

We are ready to complete the proof. $P(n,p-1)$ gives
$f(n)+d(p-1)\mid nf(n) - d(p-1)^2.$ Check that $p-1\equiv -f(n)/d\pmod{f(n)+d(p-1)}$ . So, $f(n)+d(p-1)\mid f(n)(nd-f(n))$ . Taking $p$ sufficiently large, we must have $f(n)=dn$ (recall $d=c=f(1)$ is fixed) for all $n$ , completing the proof.

Z K Y

The post below has been deleted. Click to close.

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

1490 posts

#3 h Apr 8, 2025, 3:23 AM

Y by

I have this really odd taste I've seen a very similar F.E. somewhere, idk.
Denote $P(a,b)$ the assertion of the given F.E., rearranging we have $f(a)+f(b) \mid (a+b)f(a)$ for all positive integers $a,b$ .
Now of course take $a=k$ and $b=p-k$ for some prime $p$ and $1 \le k \le p-1$ which gives $f(k)+f(p-k) \mid pf(k)$ and here if we ever had that $\gcd(f(k)+f(p-k),p)=1$ then we get $f(k)+f(p-k) \mid f(k)$ , a trivial contradiction thus $p \mid f(k)+f(p-k)$ and this means $p \mid f(k)+f(p-k) \mid pf(k)$ , so now we put our focus on a fixed constant, but before that ofc notice $P(1,a)$ gives that $f(a)+f(1) \mid af(1)+f(1)$ which gives that $f(a) \le af(1)$ for all positive integers $a$ .
Now continuing again we will put $k=1$ in order to get that $p \mid f(p-1)+f(1) \mid pf(1)$ , so let $d \mid f(1)$ a divisor of $f(1)$ then we have by Pigeonhole that there exists infinitely many primes $p$ for which $f(p-1)+f(1)=dp$ for some $d$ . So of course now we want to let $f(1)=d\ell$ and have for infinitely many primes $p$ that $f(p-1)=d(p-\ell)$ .
Denote the set of such primes as $\mathcal P$ , consider any two $q,r \in \mathcal P$ then $P(q-1,r-1)$ gives $d(q+r-2\ell) \mid d(q+r-2)(q-\ell)$ and from here we can get $q+r-2\ell \mid 2(\ell-1)(q-\ell)$ and just fix some $q>(\ell)^{1434}$ while making $r$ large enough to conclude that $\ell=1$ must always hold true and thus $f(p-1)=f(1)(p-1)$ is always in fact true.
To finish just do $P(p-1,a)$ for fixed $a$ and $p \in \mathcal P$ to get $f(a)+f(1)(p-1) \mid f(1)(p-1)(a+p-1) \mid (f(1)(p-1))^2+af(1) \cdot f(1)(p-1)$ which should give that $f(a)+f(1)(p-1) \mid f(a)(f(a)-af(1))$ so setting $p$ large gives $f(a)=af(1)$ for all positive integers $a$ by repeating the process for all, thus we are done :cool:

:cool:

.

This post has been edited 1 time. Last edited by MathLuis, Apr 8, 2025, 3:37 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a