Let $\mathbb N$ be the set of positive integers. Find all functions $f\colon\mathbb N\to \mathbb N$ such that for every $m,n\in \mathbb N$, \[ f(m)+f(n)\mid m+n. \]
Problem
Source: Swiss 2020 Final Round First Exam Problem 1
Tags: algebra, number theory, Divisibility
02.03.2020 00:34
02.03.2020 00:35
This is easy just take $P(1,1)$ then $P(p-1,1)$ and we finish by $P(p-1,n)$ where $p$ is a prime number.
02.03.2020 05:26
can someone tell where are Swiss 2020 Final Round First Exam problems.
02.03.2020 07:35
Muriatic wrote: Let $\mathbb N$ be the set of positive integers. Find all functions $f\colon\mathbb N\to \mathbb N$ such that for every $m,n\in \mathbb N$, \[ f(m)+f(n)\mid m+n. \] Answer : $f(x)=x,\forall x \in \mathbb{N}$. Put,$m=n=1$ ,get $f(1)=q$. Put,$m=n$ get $ f(m)|m$. For a prime $p=m$ ,$f(p)=p$. Again put $m=p-1,n=1$ to get $f(p-1)+1=p$. $\implies f(p-1)=p-1$. Suppose,$p>q$ and $q$ is prime Which give $f(p-q)+q=p$. $\implies f(p-q)=p-q$.now it will enough to show the next
06.09.2020 00:18
itslumi wrote: can someone tell where are Swiss 2020 Final Round First Exam problems. The Swiss MO final round problems have not all been released as there are some IMO Shortlist 2019 Problems.... I am assuming that they will be released after IMO 2020 in September when the Shortlist for IMO 2019 is released. Also, I have the problems (I was part of the final round) and therefore I can share them with you after the IMO takes place. Also, just Bertrand's postulate trivializes the problem. If anyone is interested, I could post a sol'n (that I presented in the exam). Also, P2 is another problem from the Finalround that is quite nice and easy which I could present a solution to.
06.09.2020 02:58
ftheftics wrote: Muriatic wrote: Let $\mathbb N$ be the set of positive integers. Find all functions $f\colon\mathbb N\to \mathbb N$ such that for every $m,n\in \mathbb N$, \[ f(m)+f(n)\mid m+n. \] Answer : $f(x)=x,\forall x \in \mathbb{N}$. Put,$m=n=1$ ,get $f(1)=q$. Put,$m=n$ get $ f(m)|m$. For a prime $p=m$ ,$f(p)=p$. Again put $m=p-1,n=1$ to get $f(p-1)+1=p$. $\implies f(p-1)=p-1$. Suppose,$p>q$ and $q$ is prime Which give $f(p-q)+q=p$. $\implies f(p-q)=p-q$.now it will enough to show the next With $f(p)\mid p$ we can have $f(p)=1$.
24.09.2020 10:41
Muriatic wrote: Let $\mathbb N$ be the set of positive integers. Find all functions $f\colon\mathbb N\to \mathbb N$ such that for every $m,n\in \mathbb N$, \[ f(m)+f(n)\mid m+n. \] Let $p(m.n)$ denote the assertions. First take $P(1,1)$, this gives us $2f(1)\mid 2$ ---> $f(1)\mid 1$, which gives us that $f(1)=1$. Now let $p$ be a prime number. $P(p-1,1)$, this gives us $f(p-1)+1\mid p$ , since we know that $p$ is prime we have that $f(p-1)=p-1$. Now taking $P(p-1,n)$, gives us that $p-1+f(n)\mid p-1+n$, and we can say from here that $f(n)=n$ and we are done . $\blacksquare$
24.09.2020 10:52
I have decided to include a non-standard approach to this problem. Claim: $f(n) = n$ is the only such function. We prove with strong induction. Base case: $P(1,1) \implies f(1)=1$. Assume $f(n)= n$ for all $n \leq k$. For $n=k+1$, pick some $m < k +1$ satisfying $m+k+1$ is prime, this is possible by Bertrand's postulate. Then, $P(m,k+1) \implies m + f(k+1) \mid m + k + 1$. Since $m+k+1$ is prime, this implies $m+f(k+1) = 1$ or $m+k+1$. The former is impossible. Hence $f(k+1) = k+1$ as required.
24.09.2020 12:06
idkwhatthisis wrote: I have decided to include a non-standard approach to this problem. Claim: $f(n) = n$ is the only such function. We prove with strong induction. Base case: $P(1,1) \implies f(1)=1$. Assume $f(n)= n$ for all $n \leq k$. For $n=k+1$, pick some $m < k +1$ satisfying $m+k+1$ is prime, this is possible by Bertrand's postulate. Then, $P(m,k+1) \implies m + f(k+1) \mid m + k + 1$. Since $m+k+1$ is prime, this implies $m+f(k+1) = 1$ or $m+k+1$. The former is impossible. Hence $f(k+1) = k+1$ as required. This is the solution I was talking about before, thanks for posting it
29.12.2021 21:53
$$f(p-1)=p-1$$p- is prime number $$f(n)+p-1|n-f(n)$$$$f(n)=n$$
30.03.2022 17:25
Let $p$ be any arbitrarily large prime and let $P(m,n)$ be the given assertion. $P(1,1)\Rightarrow2f(1)\mid2\Rightarrow f(1)=1$ $P(1,p-1)\Rightarrow f(p-1)+1\mid p\Rightarrow f(p-1)=p-1$ (since $f(p-1)+1>1$) $P(n,p-1)\Rightarrow f(n)+p-1\mid n+p-1\Rightarrow f(n)+p-1\mid n-f(n)\Rightarrow\boxed{f(n)=n}$ which is a solution.
30.03.2022 17:29
Under two minutes. Let $P(m,n)$ denote the given assertion. $P(1,1): 2f(1)\mid 2\implies f(1)=1$. Let $p$ be prime. $P(p-1,1): f(p-1)+1\mid p\implies f(p-1)=p-1$. $P(p-1,n): p-1+f(n)\mid p-1+n$. So $p-1+f(n)\mid p-1+f(n)+(n-f(n))\implies p-1+f(n)\mid n-f(n)$. Set $p$ sufficiently large. We get $\boxed{f(n)=n}$, which works.
26.01.2025 19:52
Denote $P(m,n)$ the assertion of the given F.E. $P(1,1)$ gives $f(1)=1$, also $P(1,p-1)$ now gives $f(p-1)=p-1$ (because $1+f(p-1)>1$) for all primes $p$, now from $P(p-1,n)$ we get that $p-1+f(n) \mid p-1+n$ therefore $p-1 \mid n-f(n)$ so take $p \to \infty$ to get $f(n)=n$ for all positive integers $n$ thus we are done .