IMO 2016 Shortlist, N6

The post below has been deleted. Click to close.

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

930 posts

#1 h Jul 19, 2017, 4:31 PM • 23 Y

Y by rafayaashary1, trashbagcheater234, Problem_Penetrator, Lam.DL.01, rkm0959, Davi-8191, Mathuzb, Amir Hossein, AlastorMoody, xymking, adityaguharoy, itslumi, centslordm, donotoven, tigerzhang, megarnie, Amkan2022, Adventure10, Mango247, jmiao, deplasmanyollari, ItsBesi, EpicBird08

Denote by $\mathbb{N}$ the set of all positive integers. Find all functions $f:\mathbb{N}\rightarrow \mathbb{N}$ such that for all positive integers $m$ and $n$ , the integer $f(m)+f(n)-mn$ is nonzero and divides $mf(m)+nf(n)$ .

Proposed by Dorlir Ahmeti, Albania

Z K Y

The post below has been deleted. Click to close.

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

v_Enhance

6877 posts

v_Enhance

#2 h Jul 19, 2017, 4:41 PM • 27 Y

Y by matol.kz, dangerousliri, kingofgeedorah, samuel, vsathiam, Amir Hossein, nguyenhaan2209, Henry_2001, xymking, mijail, A-Thought-Of-God, v4913, itslumi, centslordm, Jc426, donotoven, HamstPan38825, math31415926535, Assassino9931, Math-Star., Adventure10, Mango247, jmiao, bhan2025, BorivojeGuzic123, EpicBird08, megahertz13

The answer is $f(x) = x^2$ only, which clearly work.

First, putting $m=n=1$ gives $f(1)=1$ . Now,

Putting $m=1$ gives $f(n) -n+1 \mid nf(n) + 1$ , or equivalently, $f(n)-n+1 \mid n^2-n+1.$
Putting $m=n$ gives $2f(n)-n^2 \mid 2nf(n)$ , or equivalently, $2f(n) - n^2 \mid n^3.$

These equations are nice for philosophical reasons because they imply $f(n)$ has finitely many possible values for any $n$ . Now, the $n^3$ is especially nice when $n$ is a prime, and in fact we claim that:

Claim: For $p \ge 100$ a prime, we have $f(p) = p^2$ .

Proof. From $2f(p) - p^2 \mid p^3$ , we have that $f(p) \in \left\{ \frac{-p^3+p^2}{2}, \frac{-p^2+p^2}{2}, \frac{-p+p^2}{2}, \frac{-1+p^2}{2}, \frac{1+p^2}{2}, \frac{p+p^2}{2}, \frac{p^2+p^2}{2}, \frac{p^3+p^2}{2} \right\}.$ Of these, the first two are negative hence impossible, and $f(p) = p^2$ is what we want. So we wish to exclude the other five cases. On the other hand, we know that $2f(p) + 2p - 2 \mid 2p^2-2p+2$ and so we can just manually check the five cases by hand (each in a routine way). $\blacksquare$

Once we have arbitrarily large primes, we are happy. Fix any $n$ . Letting $m$ be a prime gives $p^2 + f(n) - pn \mid p^3 + nf(n) \iff p^2 + f(n) - pn \mid p^3 - np^2 + pn^2.$ By considering only $p > f(n)$ we may drop the factor of $p$ on the right, so $p^2 + f(n) - pn \mid p^2 - np + n^2 \iff p^2 + f(n) - pn \mid n^2 - f(n).$ By taking $p$ large, we conclude $f(n) = n^2$ .

Z K Y

The post below has been deleted. Click to close.

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

matol.kz

21 posts

matol.kz

#3 h Jul 19, 2017, 4:57 PM • 3 Y

Y by centslordm, Adventure10, Mango247

you have already solved these problems a long time ago)

Z K Y

The post below has been deleted. Click to close.

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

USJL

540 posts

USJL

#4 h Jul 20, 2017, 2:55 AM • 3 Y

Y by centslordm, Adventure10, ehuseyinyigit

This problem has emerged on AOPS like two years ago... very weird...

Z K Y

The post below has been deleted. Click to close.

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

v_Enhance

6877 posts

v_Enhance

#5 h Jul 20, 2017, 12:59 PM • 12 Y

Y by Jetze, rightways, WindTheorist, Aryan-23, v4913, centslordm, Jc426, HamstPan38825, megarnie, Adventure10, aidan0626, ehuseyinyigit

matol.kz wrote:

you have already solved these problems a long time ago)

Yes, I was an organizer for the American training camp (MOP), and I designed the mock exams for the camp using problems from the IMO Shortlist. This meant I had to solve (or try to solve

) all the problems myself.

This post has been edited 1 time. Last edited by v_Enhance, Jul 20, 2017, 12:59 PM

Z K Y

The post below has been deleted. Click to close.

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

tenplusten

1000 posts

tenplusten

#6 h Jul 20, 2017, 8:59 PM • 4 Y

Y by CANBANKAN, centslordm, Adventure10, Mango247

I think when Dorlir Ahmeti says that his problem is difficulter than actual P3 he was speaking about N6.But isn't it too easy

Z K Y

The post below has been deleted. Click to close.

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

dangerousliri

930 posts

dangerousliri

#7 h Jul 20, 2017, 9:12 PM • 3 Y

Y by centslordm, Adventure10, Mango247

Murad.Aghazade wrote:

I think when Dorlir Ahmeti says that his problem is difficulter than actual P3 he was speaking about N6.But isn't it too easy

Sorry I was mistaken, maybe I said that because I want it my problem to be P3, but is not easy problem.

This post has been edited 3 times. Last edited by dangerousliri, Jul 20, 2017, 10:15 PM

Z K Y

The post below has been deleted. Click to close.

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

HECAM-CA-CEBEPA

13 posts

HECAM-CA-CEBEPA

#8 h Jul 22, 2017, 9:12 AM • 4 Y

Y by dangerousliri, centslordm, Adventure10, Mango247

This was also problem 2 at Bosnia Herzegovina TST 2017

This post has been edited 1 time. Last edited by HECAM-CA-CEBEPA, Jul 23, 2017, 12:21 PM

Z K Y

The post below has been deleted. Click to close.

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

Kezer

986 posts

Kezer

#9 h Jul 22, 2017, 9:53 AM • 3 Y

Y by centslordm, Adventure10, Mango247

Also German TSTST #3.

Z K Y

The post below has been deleted. Click to close.

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

Kayak

1298 posts

Kayak

#10 h Jan 30, 2018, 6:44 AM • 4 Y

Y by centslordm, Adventure10, Mango247, BorivojeGuzic123

My solution is exactly same as that of v_Enhance, but posting it anyway.

Solution

As a sidenote, how this is N6

Clearly even the N3 is way harder than this.

This post has been edited 1 time. Last edited by Kayak, Jan 30, 2018, 6:48 AM

Z K Y

The post below has been deleted. Click to close.

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

yayups

1614 posts

yayups

#11 h Dec 22, 2018, 11:33 AM • 3 Y

Y by centslordm, Adventure10, Mango247

Nice problem:

I claim only $f(x)=x^2$ works, and this is easy to check. Suppose $f$ is a solution. Let $g(x)=f(x)-x^2$ . Then, we have
$g(m)+g(n)+(m^2+n^2-mn)\mid mg(m)+ng(n)+m^3+n^3.$ Subtracting $m+n$ times the left from the right, we get
$g(m)+g(n)+(m^2+n^2-mn)\mid ng(m)+mg(n).$ Call this statement $P(m,n)$ . We see that $P(n,n)$ implies $2g(n)+n^2\mid 2ng(n)$ , so $2g(n)+n^2\mid n^3$ , or $2f(n)-n^2\mid n^3$ . Letting $n=1$ , we see that $2f(1)-1\mid 1$ , so $2f(1)=1\pm 1=0,2$ . But $f(1)\ge 1$ , so $f(1)=1$ . Now, letting $n=p$ be prime, we see that
$2f(p)-p^2\in\pm\{1,p,p^2,p^3\}.$ Using the condition that $f(p)>0$ , we get that
$f(p)\in\left\{\frac{p^2-p}{2},\frac{p^2-1}{2},\frac{p^2+1}{2},\frac{p^2+p}{2},p^2,\frac{p^2+p^3}{2}\right\}.$ Let's look at $P(p,1)$ now. We get that
$g(p)+(p^2-p+1)\mid g(p),$ so $f(p)-p+1\mid p^2-p+1$ .

Case 1: $f(p)=\frac{p^2-p}{2},\frac{p^2-1}{2},\frac{p^2+1}{2},\frac{p^2+p}{2}$ .
We'll just do the first part, the rest follow similarly. Here, we get that $p^2-p-2p+2\mid 2(p^2-p+1)$ , so $p^2-3p+2\mid 2p^2-2p+1$ , so $p^2-3p+2\mid 4p-3$ . For large enough $p$ this is a contradiction.

Case 2: $f(p)=\frac{p^2+p^3}{2}$ .
Here, the left side $f(p)-p+1$ is bigger than the right side for large enough $p$ , so this is a contradiction.

Thus, for large enough primes $p$ , we get that $f(p)=p^2$ , so $g(p)=0$ . Now, $P(m,p)$ then implies
$g(m)+(m^2+p^2-mp)\mid p(m^2+p^2-mp).$ Suppose $g(m)\not=0$ . We have that
$\frac{p(m^2+p^2-mp)}{g(m)+m^2+p^2-mp}=p-\frac{pg(m)}{g(m)+m^2+p^2-mp}\in\mathbb{Z}\setminus\{p\},$ so
$\frac{pg(m)}{g(m)+m^2+p^2-mp}\in\mathbb{Z}\setminus\{0\}.$ Taking $p$ to be very large, we see that the left side is on order $1/p$ , so it eventually has norm less than $1$ , a contradiction. Therefore, we must have $g(m)=0$ , so $f(m)=m^2$ for all $m$ , as desired. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

mastermind.hk16

143 posts

mastermind.hk16

#12 h Feb 11, 2019, 1:52 AM • 2 Y

Y by centslordm, Adventure10

The only solution is $f(n)=n^2$ .
Throughout the solution, denote $(x,y)$ as plugging $m=x,n=y$ into the functional equation.
$(1,1) \longrightarrow 2f(1)-1 \mid 2f(1) \Longrightarrow f(1)=1$

Let $p \geq 5$ be an odd prime.
$(p,p) \longrightarrow 2f(p) -p^2 \mid 2p^3$
Hence $f(p) \in \{ \frac{p^2 \pm 1}{2} , \frac{p^2 \pm p}{2}, p^2 , \frac{p^3+p^2}{2}\}$
$(p,1) \longrightarrow f(p) -p+1 \mid pf(p) +1 \Longleftrightarrow f(p) -p+1 \mid p^2 - p +1 \Longleftrightarrow f(p)-p+1 \mid p^2-2f(p) +p -1$

If $f(p) = \frac{p^2 \pm 1}{2}$ then $\frac{p^2 \pm 1}{2} -p+1 \mid p-1 \mp 1 \Longleftrightarrow p^2 \pm 1 -2p+2 \mid 2p-2\mp 2$
But $0 < 2p-2 \mp 2 +2p -2\leq 4p-2 < p^2 \pm 1$ so not possible.

If $f(p)=\frac{p^2 + p}{2}$ then $\frac{p^2 + p}{2} -p+1 \mid p^2 -p+1 \Longleftrightarrow p^2-p+2 \mid p^2 - p$ impossible
If $f(p) =\frac{p^2-p}{2}$ then $p^2 -3p +2 \mid 4p$ again not possible.

If $f(p)= \frac{p^3+p^2}{2}$ then $\frac{p^3+p^2}{2}-p+1 \mid p^2 -p+1 \Longleftrightarrow p^3 +p^2 -2p+1 \mid 2p^2 -2p+2$ not possible.
Hence $f(p)=p^2 \ \ \forall p\geq 5$

$(p,n) \longrightarrow p^2 +f(n) -np \mid p^3 +nf(n)$
$p^3 +nf(n) \equiv p^3 +n(np-p^2) \equiv n^2p -pf(n) \mod (p^2+f(n)-np)$ Take $p$ sufficiently large such that $p^2> n^2p -pf(n)-f(n)+np$ such a prime exists since the LHS is a quadratic in $p$ while RHS is linear. Then
$n^2 p -pf(n) < p^2 +f(n) -np$ so $f(n)=n^2 \ \ \forall n \in \mathbb{N}$ . Done.

This post has been edited 1 time. Last edited by mastermind.hk16, Feb 11, 2019, 1:56 AM

Z K Y

The post below has been deleted. Click to close.

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

Pluto1708

1107 posts

Pluto1708

#13 h Feb 11, 2019, 4:52 AM • 3 Y

Y by centslordm, Adventure10, Mango247

@v_enhance your proof is nice but I think that this might be a typo here

v_enhance wrote wrote:

Claim: For $p \ge 100$ a prime, we have $f(p) = p^2$ .

Why $p>100$ ?

Z K Y

The post below has been deleted. Click to close.

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

stroller

894 posts

stroller

#14 h Feb 11, 2019, 12:53 PM • 2 Y

Y by centslordm, Adventure10

@above
It's just saying concretely 100 is sufficient instead of saying it holds for all large $p$ .This is just to avoid edge cases like $p=2$ that unnecessarily complicates the discussion.

Z K Y

The post below has been deleted. Click to close.

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

ubermensch

820 posts

ubermensch

#15 h Sep 7, 2019, 6:18 AM • 3 Y

Y by AlastorMoody, centslordm, Adventure10

Yay solved a $6$ ! (though this one's not too tough though)

First let's get over with the obvious substitutions-
$P(m,m): 2f(m)-m^2 \mid 2mf(m) => 2f(m)-m^2 \mid m^3$ . Putting $m=1$ gives you $2f(1)-1 \mid 1 => f(1)=1$ .
$P(m,1): f(m)-m+1 \mid m^2-m+1 -m(f(m)-m+1) =>f(m)-m+1 \mid m^2-m+1$ (Corollary which'll be useful: $f(m) leq m^2$ .

Fine, we already have quite a bit of information, and it's clear that there's probably going to be no way to solve a "functional divisibility" purely through algebraic manipulation- well let's just put in primes then, eh?

For $p$ prime:
$P(p,p): 2f(p) -p^2 \mid p^3$ . Hey this seems pretty useful- it means $2f(p)-p^2$ must be equal to one of $(+-1,+-p,+-p^2,+-p^3)$ .
Well, we've got nothing much else to do, and it pretty much seems like $f(x)=x^2$ has got to be the only solution, so let's just bash it out using $f(m)-m+1 \mid m^2-m+1$ ? (and I promise it gets easier as you got through the cases)

Case 1: $2f(p)-p^2=1 =>f(p)=\frac{p^2+1}{2}$
Thus $\frac{p^2+1}{2} -p+1 \mid p^2-p+1 => p^2-2p+3 \mid p^2-p+1 =>p^2-2p+3 \mid p-2 \neq$ possible.

Case 2: $2f(p)-p^2 =-1 => f(p)=\frac{p^2-1}2$
Thus $\frac{p^2-1}2 -p+1 \mid p^2-p+1 =>p^2-2p+1 \mid 2p^2-2p+1-2(p^2-2p+1) =>p^2-2p+1 \mid 2p-1 \neq$ possible for $p \geq 5$ .

Case 3: $2f(p)-p^2=p=>f(p)=\frac{p^2+p}2$
Thus $\frac{p^2+p}2 -p+1 \mid p^2-p+1=>p^2-p+2 \mid 2p^2-2p+2 =>p^2-p+2 \mid 2 \neq$ possible.

Case 4: $2f(p)-p^2=-p =>f(p)=\frac{p^2-p}2$
Thus $\frac{p^2-p}{2} -p+1 \mid p^2-p+1 =>p^2-3p+2 \mid 2p^2-2p+2 =>p^2-3p+2 \mid 4p-2 \neq$ possible for $p \geq 7$ .

Case 5: $2f(p)-p^2=-p^2 =>f(p)=0 \neq$ possible.

Case 6: $2f(p)-p^2 =+-p^3$
$2f(p)-p^2=-p^3=>f(p)=\frac{p^2-p^3}2 <0 \neq$ possible for $p \geq 2$ , and $2f(p)-p^2=p^3 \neq$ possible as $f(p) \leq p^2$ for $p \geq 2$

Aha, so which case did I sneakily not include when listing out these cases which end up not working- well, of course $f(p)=p^2$ , which works for all $p$ . Thus we can conclude $f(p)=p^2$ for $p \geq 7$ .

Now the problem's pretty easy to finish off- for a fixed $m$ , choose some prime $p$ such that $(p,m)=(p,f(m))=1$ .
$P(m,p): f(m)+p^2-mp \mid p^3+mf(m) =>f(m)+p^2-mp \mid p^3 +mf(m)-m(f(m)+p^2-mp)=p(p^2-mp+m^2)$ .

As $(p,f(m))=1 =>f(m)-mp+p^2 \mid p^2-mp+m^2=> f(m)-mp+p^2 \mid m^2-f(m)$ . Notice that we can choose arbitrarily large $p$ such that $p^2-mp+f(m)$ becomes arbitrarily large while $m^2-f(m)$ stays fixed- thus $f(m)-m^2$ must equal $0$ $=>f(m)=m^2$ .

Thus the only solution is $f(m)=m^2$ , and it obviously works, hence we're done.

This post has been edited 1 time. Last edited by ubermensch, Sep 7, 2019, 6:18 AM

Z K Y

The post below has been deleted. Click to close.

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

ismayilzadei1387

219 posts

ismayilzadei1387

#55 h Oct 28, 2023, 6:52 PM • 1 Y

Y by FriIzi

Oh wowww(Shukur!!!) I just Solved My first N6
$f(m)+f(n)-mn | mf(m)+nf(n)$
$P(1,1)$ $\implies$ $f(1)=1$
Let's take any Prime $p$
From $P(1,p)$ $p^2 \geq f(p)$
$P(p,p)$
$2f(p)-p^2 | 2pf(p)$
$2f(p)-p^2| p^3$
So that $f(p)= \frac{p^2+1}{2} ; \frac{p^2+p}{2} ; p^2$
Case1: $f(p)=p^2$
$P(m,p)$
$f(m)+p^2-pm | mf(m)+p^3$
$f(m)+p^2-pm |p(p^2-pm+m^2)$
$f(m)+p^2-pm | m^2-f(m)$
Let's take $p$ sufficiently large so $f(m)=m^2$
Case 2: $f(p)=\frac{p^2+p}{2}$
$P(1,p)$
$p^2-p+2 | 2p^2-4p+2$
$p^2-p+2 | 2p-2$
$p^2+4 \le 3p$ but with $AM-GM$ $p^2+4 \geq 4p$ so contradicition.
Case 3: $f(p)=\frac{p^2+1}{2}$
$P(1,p)$
$p^2-2p+5 | 2p^2-2p+2$
$p^2-2p+5 |2p-8$
Also By $AM-GM$ that is contradicition.
So $f(m)=m^2$ is unique solution.....

Z K Y

The post below has been deleted. Click to close.

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

HamstPan38825

8857 posts

HamstPan38825

#56 h Dec 17, 2023, 4:27 PM

Y by

Setting $m=n=1$ , we have $2f(1) - 1 \mid 1$ , or $f(1) = 1$ . Setting $m=n$ and $m=1$ respectively, we have the two relations
$\begin{align*} 2f(m) - m^2 &\mid m^3 \\ 1+f(n) - n &\mid n^2-n-1. \end{align*}$ Setting $m=p$ in the first relation yields $f(p) \in \left\{\frac{p^2+p^3}2, p^2, \frac{p^2+p}2, \frac{p^2+1}2\right\}.$ On the other hand, $f(p) \leq p^2$ by the second relation. Now, for sufficiently large $p$ ,
$\begin{align*} \frac 12(p^2-p+2) &\nmid p^2-p-1 \\ \frac 12(p^2-2p+3) &\nmid p^2-p-1 \end{align*}$ which eliminates all options but $f(p) = p^2$ .

Now we can extend to all $n$ . Note that we have $p^2+f(n) - np \mid p^3 + nf(n),$ so we can in fact write $p^2+f(n) - np \mid p^3+nf(n) - (p+n)(p^2+f(n)-np) = p(f(n) - n^2).$ By picking sufficiently large $p$ , the LHS is relatively prime to $p$ , and furthermore it exceeds $f(n) - n^2$ . This shows $f(n) = n^2$ .

Z K Y

The post below has been deleted. Click to close.

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

kamatadu

478 posts

kamatadu

#57 h Jan 4, 2024, 7:21 PM

Y by

The solution is $f(x) \equiv x^2$ .

$P(m,m) \implies 2f(m) - m^2 \mid 2mf(m) \equiv m^3$ .
Now we substitute $m=1$ in this to get $f(1) = 1$ .

Now $P(m,1) \implies f(m) + 1 - m \mid mf(m) + 1 \equiv m^2 - m + 1$ . Then we get that $f(m) \le m^2 \implies 2f(m) - m^2 \le m^2$ .

Now in $2f(m) - m^2 \mid m^3$ , pick $m = p$ where $p$ is an odd prime. Then we get $2f(p) - p^2 \mid p^3$ . But from the bound we got earlier, we get that only $\left\{-p,1,p,p^2\right\}$ might work.

Now testing each possible value for $f(p)$ that we might get from above by substituting it into $f(m) + 1 - m \mid m^2 - m + 1$ , we get that only $f(p) = p$ works.

Now we can also find $f(2)$ by setting $m=2$ and then comparing the values we get from $f(m) + 1 - m \mid m^2 - m + 1$ and $2f(m) - m^2 \mid m^3$ . This gives us $f(2) = 2$ .

Thus we get that $f(p) = p$ for all prime $p$ .

Now fix some $k \in \mathbb Z$ , and we are going to find out $f(k)$ .

Let $S$ be the set of primes that are co-prime with $f(k)$ .

Now $P(k,p) \implies f(k) + p^2 - kp \mid kf(k) + p^3 \equiv p^3 - kp^2 + k^2p = p(p^2 - kp + k^2)$ . Now note that $\gcd(f(k) + p^2 -kp,p) = 1$ . Then we can reduce the previous condition to $f(k) + p^2 - kp \mid p^2 - kp + k^2 \equiv k^2 - f(k)$ . But then note that we can take sufficiently large $p$ to prove that $k^2 \equiv f(k) \implies f(k) = k^2$ and we are done. :yoda:

Z K Y

The post below has been deleted. Click to close.

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

ATGY

2502 posts

ATGY

#58 h Mar 1, 2024, 1:04 PM

Y by

hurrah my firs n6

Let $P(x, y)$ be the given assertion. $P(1, 1)$ gives $2f(1) - 1 \mid 2f(1) \implies f(1) = 1$ . Take $p$ to be a prime, $P(p, 1)$ :
$f(p) + 1 - p \mid pf(p) + 1 \implies f(p) + 1 - p \mid p^2 - p + 1$ This means $f(p) \leq p^2$ , and since $p^2 - p + 1$ is odd, either $f(p) = p^2$ , or $p^2 - p + 1 > 3f(p) + 3 - 3p \implies \frac{p^2 + 2p - 2}{3}$ . $P(p, p)$ gives $2f(p) - p^2 \mid p^3$ , however plugging in the inequality back in we find that it's cannot be a divisor of $p^3$ (as it must be $-p$ or $-p^2$ ).

So, $f(p) = p^2$ . $P(p, n)$ gives:
$p^2 + f(n) - pn \mid p^3 + nf(n) \implies p^2 + f(n) - pn \mid p^3 + nf(n) - n(p^2 + f(n) - pn) = p^3 - np^2 + pn^2$ For sufficiently large $p$ , we have:
$p^2 + f(n) - pn \mid p(p^2 - np + n^2) \implies p^2 + f(n) - pn \mid p^2 - np + n^2 \implies p^2 + f(n) - pn \mid p^2 - np + n^2 - p^2 - f(n) + pn = n^2 - f(n)$ This means that $n^2 - f(n) = 0 \implies f(n) = n^2$ , so we are done.

Z K Y

The post below has been deleted. Click to close.

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

shendrew7

794 posts

shendrew7

#59 h Mar 18, 2024, 2:44 AM

Y by

We claim our only solution is $\boxed{f(x)=x^2}$ , which works. Denote the assertion as $A(m,n)$ . First note $A(1,1)$ gives $f(1)=1$ . Consider a prime $p$ :

$A(p,p)$ tells us $2f(p)-p^2 = \pm 1, \pm p, \pm p^2, \pm p^3$ , as
$2f(p)-p^2 \mid (2pf(p)) - p(2f(p)-p^2) = p^3.$
Using $A(p,1)$ , casework on our previous 8 values tells us we can only have $f(p)=p^2$ for large $p$ , as
$f(p)-p+1 \mid (pf(p)+1) - p(f(p)-p+1) = p^2-p+1.$

Notice our condition can be rewritten as
$f(m)+f(n)-mn \mid (m+n)(f(m)+f(n)-mn) - (mf(m)+nf(n))$ $f(m)+f(n)-mn \mid m(f(n)-n^2)+n(f(m)-m^2).$
Fix $n$ as any natural. Setting $m=p$ as an arbitrarily large prime, we require
$f(n)+p(1-n) \mid f(n)-n^2,$
and since we can force $|f(n)+p(n-1)| > |f(n)-n^2|$ using large $p$ , we must have $f(n)=n^2$ for all $n$ , as desired. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

bjump

1007 posts

bjump

#60 h Jul 2, 2024, 3:11 AM

Y by

We claim the answer is $f(x)=x^2$ .

Setting $m=n=1$ implies $f(1)=1$ . Consider a prime $p$ , then setting $m=n=p$ then $\begin{align*} 2f(p)-p^2 \mid 2pf(p) &\stackrel{\text{EA}}\iff 2f(p)-p^2 \mid p^3 \\ \implies 2f(p)-p^2 &\in \{\pm 1, \pm p, \pm p^2, \pm p^3 \} \end{align*}$ Manually checking each of these cases relatively routine testing gives that $f(p)=p^2$ for prime $p$ . Now consider $m$ and a sufficiently large prime $p$ with $f(m)<p$ . Then $p^2+f(m)-pm \mid p^3+mf(m) \stackrel{\text{EA}}\iff p^2+f(m)-pm \mid p^3-mp^2+pm^2$ . However $f(m)<p$ implies that the LHS is not divisible by $p$ so we require $p^2+f(m)-pm \mid p^2-mp+m^2 \stackrel{\text{EA}}\iff p^2+f(m)-pm \mid f(m)-m^2$ . However as $p$ grows the LHS grows without bound while the RHS is fixed, therefore the RHS is $0$ or $f(m)=m^2$ for all $m$ , and we are finished. $\square$

Z K Y

The post below has been deleted. Click to close.

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

cursed_tangent1434

606 posts

cursed_tangent1434

#61 h Dec 24, 2024, 12:13 PM

Y by

First note that clearly $f(1)=1$ . Then, consider a prime $p$ . We then have $2f(p)-p^2 \mid 2pf(p) \implies 2f(p)-p^2\mid p^3$ . This gives us seven cases for what $2f(p)-p^2$ is ( $1,p,-p,p^2,-p^2.p^3,-p^3$ ). One can check all these cases and see that for sufficiently large primes $p$ we must have $f(p)=p^2$ . Clearly, $f(n)+f(1)-n \mid nf(n)+f(1) \implies f(n)-n+1\mid n^2-n+1$ . This gives us that $f(n)\leq n^2$ . Thus, we consider an integer $n$ and an arbitrarily large prime $p$ ( $p>n^2+n$ ). This gives us that
$p^2-pn+f(n) \mid p^3+nf(n) \implies p^2-pn+f(n) \mid pf(n)-pn^2$ with some manipulation. Now, notice that we must have
$p^2-pn+f(n)\leq pn^2-pf(n)\implies (p+1)f(n)\leq p(n^2+n-p)<0$ which is a clear contradiction which implies that we must have $pn^2-pf(n)=0$ which requires $f(n)=n^2$ for all $n$ and we are done.

Z K Y

The post below has been deleted. Click to close.

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

AshAuktober

998 posts

AshAuktober

#62 h Dec 30, 2024, 5:43 AM

Y by

Nice!

We claim the only solution is $f(x) = x^2$ , which satisfies the equation.
Sketch of proof:
$P(1, 1)$ \implies $f(1) = 1$ .
$P(p, p)$ for $p$ primes gives some values of $f(p)$ , most of which can be checked to fail for p large, apart from $f(p) = p^2$ .
So indeed $f(p) = p^2$ for all $p$ large.
Now consider $P(x, p)$ with $p > x^2$ , simplifying we get $f(x)-xp+p^2 \mid x^2-f(x)$ .
But now $x^2-f(x)$ has infinitely many divisors, thus it must be zero, implying the result. QED

Z K Y

The post below has been deleted. Click to close.

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

MuradSafarli

106 posts

MuradSafarli

#63 h Dec 30, 2024, 2:04 PM

Y by

dangerousliri wrote:

Denote by $\mathbb{N}$ the set of all positive integers. Find all functions $f:\mathbb{N}\rightarrow \mathbb{N}$ such that for all positive integers $m$ and $n$ , the integer $f(m)+f(n)-mn$ is nonzero and divides $mf(m)+nf(n)$ .

Proposed by Dorlir Ahmeti, Albania

I think Nt6 could have been more difficult.

Z K Y

The post below has been deleted. Click to close.

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

ihategeo_1969

217 posts

ihategeo_1969

#64 h Jan 2, 2025, 3:06 PM • 1 Y

Y by babarazamtruefan152-0

MuradSafarli wrote:

dangerousliri wrote:

Denote by $\mathbb{N}$ the set of all positive integers. Find all functions $f:\mathbb{N}\rightarrow \mathbb{N}$ such that for all positive integers $m$ and $n$ , the integer $f(m)+f(n)-mn$ is nonzero and divides $mf(m)+nf(n)$ .

Proposed by Dorlir Ahmeti, Albania

I think Nt6 could have been more difficult.

This problem is pretty easy (I would say this and 2005 N6 are easiest N6s in the 21st century).

Z K Y

The post below has been deleted. Click to close.

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

RedFireTruck

4221 posts

RedFireTruck

#65 h Jan 12, 2025, 12:47 AM

Y by

Plugging in $m=n=1$ gives $(2f(1)-1)|(2f(1))$ so $f(1)=1$ .

Plugging in $n=1$ gives $(f(m)+1-m)|(mf(m)+1)$ so $(f(m)+1-m)|(1-m+m^2)$ .

This also tells us that $f(m)\le m^2$ .

Plugging in $m=n$ gives $(2f(m)-m^2)|(2mf(m))$ so $(2f(m)-m^2)|m^3$ .

This also tells us that $f(p)=p^2$ for prime $p$ .

This is because $f(p)=\frac{p^2\pm p}{2}$ would give $\frac{2+(-2\pm 1)p+p^2}{2}|(1-p+p^2)$ , which is absurd.

This also tells us that $(f(m)+p^2-mp)|(mf(m)+p^3)$ for all prime $p$ .

This simplifies into $(f(m)+p^2-mp)|(p^3-mp^2+m^2p)$ .

Note that $\frac{p^3-mp^2+m^2p}{f(m)+p^2-mp}=p+\frac{p(m^2-f(m))}{f(m)+p^2-mp}$ .

We pick $p>69420m^2$ to get $(f(m)+p^2-mp)|(m^2-f(m))$ .

This implies $f(m)=m^2$ , because otherwise, the RHS is much smaller than the LHS.

Therefore, the only solution is $\boxed{f(x)=x^2}$ .

This works because $(m^2+n^2-mn)(m+n)=m^3+n^3$ .

Z K Y

The post below has been deleted. Click to close.

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

OronSH

1729 posts

OronSH

#66 h Feb 22, 2025, 7:35 PM • 2 Y

Y by megarnie, gvh300

We claim $f(x)=x^2$ which clearly works.

From $P(p,p)$ we get $2f(p)-p^2\mid 2pf(p)$ so $2f(p)-p^2\mid p^3$ . Thus $f(p)\in\left\{p^2,\frac{p^2+1}2,\frac{p^2+p}2,\frac{p^2+p^3}2,\frac{p^2-1}2,\frac{p^2-p}2\right\}.$ Next $P(1,1)$ gives $f(1)=1$ and $P(1,p)$ gives $f(p)-p+1\mid 1+pf(p)$ so $f(p)-p+1\mid p^2-p+1$ . Checking all possibilities for $f(p)$ , we get the first one works, the fourth one fails by size, and the others reduce by euclidean algorithm to a quadratic in $p$ dividing a linear or constant, which fails or large $p$ . Thus $f(p)=p^2$ for infinitely many $p$ .

Next $P(p,n)$ gives $p^2-pn+f(n)\mid p^3+nf(n)$ , or $p^2-pn+f(n)\mid p^3-p^2n+pn^2$ . For $p>f(n)$ we get $p\nmid p^2-pn+f(n)$ so $p^2-pn+f(n)\mid p^2-pn+n^2$ , or $p^2-pn+f(n)\mid n^2-f(n)$ for infinitely many $p$ . Thus $n^2-f(n)=0$ for all $n$ as desired.

Z K Y

The post below has been deleted. Click to close.

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

john0512

4184 posts

john0512

#67 h Feb 23, 2025, 4:48 AM • 1 Y

Y by OronSH

The answer is $f(n)=n^2$ only.

Note that $f(1)=1$ by plugging in $(1,1)$ . The main claim is the following.

Claim: For all sufficently large primes $p$ , we have $f(p)=p^2$ .

By plugging in $(p,p)$ , we have
$2f(p)-p^2\mid 2pf(p)$ $2f(p)-p^2\mid p^3.$ This means that
$f(p)=\frac{p^2+\{-p,-1,1,p,p^2,p^3\}}{2}.$
Howver, by plugging in $(p,1)$ , we also have
$f(p)-p+1\mid pf(p)+1$
$f(p)-p+1\mid p^2-p+1.$ For sufficently large $p$ ,
$\frac{p^2-p}{2}$ , $\frac{p^2-1}{2}$ , $\frac{p^2+1}{2}$ do not work because they lead to the LHS being a tiny amount under half of the RHS.
$\frac{p^2+p}{2}$ does not work because it results in the LHS being $\frac12$ larger than half the RHS.
$\frac{p^2+p^3}{2}$ does not work because it results in the LHS being far too large.

Thus we conclude that $f(p)=p^2$ for all sufficently large $p$ .

Now, plug in $(m,p)$ for any $m$ and sufficently large $p$ . We have
$f(m)+p^2-mp\mid mf(m)+p^3$ $f(m)+p^2-mp\mid mf(m)+p^3-mf(m)-mp^2+m^2p$ $f(m)+p^2-mp\mid p(p^2-mp+m^2).$
For sufficently large $p$ , $p$ does not divide $f(m)$ , so the LHS is not divisible by $p$ . This can then be strengthened to
$f(m)+p^2-mp \mid p^2-mp+m^2$ $f(m)+p^2-mp\mid m^2-f(m).$ Clearly this requires $m^2-f(m)=0$ as we take sufficently large $p$ , done.

Z K Y

The post below has been deleted. Click to close.

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

InterLoop

280 posts

InterLoop

#68 h Apr 15, 2025, 12:28 AM

Y by

solution

Z K Y

The post below has been deleted. Click to close.

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

Ilikeminecraft

607 posts

Ilikeminecraft

#69 h Apr 25, 2025, 4:14 PM

Y by

Take $m = n = 1$ to give $f(1) = 1.$ $(1, 2)$ gives $f(2) = 4.$ Take $(p, p)$ and then $(1, p)$ for some prime $p$ . By testing all 6 cases, we get that $f(p) = p^2$ for all primes. Take $(p, n)$ which gives $p^2 + f(n) - np\mid p^3 + nf(n) \implies p^2 + f(n) - np \mid p^3 - np^2 + n^2p.$ Since $f(n)$ can't be divisble by every prime, we can assume it is relatively prime to $p.$ Hence, $p^2 + f(n) - np \mid p^2 - np + n^2 \implies p^2 + f(n)-np \mid n^2 - f(n).$

Z K Y