Function number theory

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

Function number theory

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Iran second round 2016,day2,problem6

The post below has been deleted. Click to close.

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

532 posts

K.N

#1 h Apr 29, 2016, 11:07 AM • 2 Y

Y by Adventure10, Mango247

Find all functions $f: \mathbb N \to \mathbb N$ Such that:
1.for all $x,y\in N$ : $x+y|f(x)+f(y)$
2.for all $x\geq 1395$ : $x^3\geq 2f(x)$

This post has been edited 1 time. Last edited by K.N, Apr 29, 2016, 11:15 AM

Z K Y

The post below has been deleted. Click to close.

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

824 posts

andria

#3 h Apr 29, 2016, 2:04 PM • 5 Y

Y by Dadgarnia, Wizard_32, Elyson, Adventure10, Mango247

too easy problem:

My solution:
$x=y\Longrightarrow x\mid f(x)$ . so there exist a function $g:\mathbb{N}\longrightarrow \mathbb{N}$ such that $f(x)=xg(x)\Longrightarrow x+y\mid xg(x)+yg(y) ,x^2\geq 2g(x)$ .
notice that $y\equiv -x\pmod{x+y}$ hence $x+y\mid xg(x)-xg(y)$ if $(x,y)=1\Longrightarrow x+y\mid g(x)-g(y) \Longrightarrow$ if $(n,x)=1 , n\mid g(n-x)-g(x)$
now take an arbitrary large odd number $n$ and an arbitrary odd number $x$ such that $(x,n)=1$ then note that:
$n\mid 2n\mid g(2n-x)-g(x) (i)$ and $n\mid g(n-x)-g(x) (ii)$
from $(i) , (ii)$ we get $n\mid g(2n-x)-g(n-x)$
Also from $\bigstar$ we get $3n-2x\mid g(2n-x)-g(n-x)$ . since $(n,3n-2x)=1$ we get $n(3n-x)\mid g(2n-x)-g(n-x)\Longrightarrow \frac{(2n-x)^2}{2} \geq n(3n-x)\Longleftrightarrow x^2\geq 2n^2$ but the last inquality is false hence $g(2n-x)=g(n-x)$ for every odd $x$ such that $(n,x)=1$ and $2n-x\ge 1395 \bigstar\bigstar$ . take two arbitrary large enough integers $a,b\in \mathbb{N}$ such that $(a,b)=1$ and $a\equiv 1\pmod{2}, b\equiv 0\pmod{2}$ . take $n=a-b,x=a-2b$ then because $n,x$ are both odd and $(n,x)=1$ from $\bigstar\bigstar$ we get $g(a)=g(b)=t$ hence for a fixed number $b$ there is a constant number $t=g(b)$ such that for infinitely many integers $x$ : $t=g(b)=g(x)\Longrightarrow f(x)=tx$ .
take suffiently large number $x$ such that $f(x)=tx$ then from main problem we get $x+y\mid xt+f(y)$ ( $y$ is arbitrary) $\Longrightarrow x+y\mid f(y)-yt$ but the left hand side is larger than the right hand side for large enough $x$ hence we must have $f(y)=yt$ for every $y\in\mathbb{N}$ at last $t\leq \frac{x^2}{2}$ for $x\geq 1395$ hence $t\leq \frac{1395^2}{2}$ . so the only solutions are $f(x)=tx$ where $t\leq \frac{1395^2}{2}$ is fixed.
Q.E.D

This post has been edited 1 time. Last edited by andria, Apr 30, 2016, 3:46 AM

Z K Y

The post below has been deleted. Click to close.

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

4900 posts

#4 h Apr 29, 2016, 2:19 PM • 2 Y

Y by Adventure10, Mango247

Andria, you lost last condition in the end.
$2tx\leq x^3$ for $x\geq 1395$ , so $t\leq \frac{1395^2}{2}$
$t \in [1,973012]$

Z K Y

The post below has been deleted. Click to close.

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

311 posts

#5 h Apr 29, 2016, 5:06 PM • 2 Y

Y by Adventure10, Mango247

Post was deleted

This post has been edited 1 time. Last edited by sepehrOp, May 1, 2016, 4:24 AM

Z K Y

The post below has been deleted. Click to close.

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

11 posts

#6 h Apr 29, 2016, 6:42 PM • 2 Y

Y by Adventure10, Mango247

who is the author of the problem?

Z K Y

The post below has been deleted. Click to close.

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

27 posts

#7 h Apr 30, 2016, 7:39 PM • 2 Y

Y by Adventure10, Mango247

sepehrOp wrote:

K.N wrote:

Find all functions $f: \mathbb N \to \mathbb N$ Such that:
1.for all $x,y\in N$ : $x+y|f(x)+f(y)$
2.for all $x\geq 1395$ : $x^3\geq 2f(x)$

we know that for large $x$ we have $a <= \frac{x^2}{2}$ (related to condition 2) so we can see that LHS is increasing and the RHS is going to be little than LHS . so $b=a$ .

Can you explain this?

Z K Y

The post below has been deleted. Click to close.

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

311 posts

#8 h May 1, 2016, 4:21 AM • 2 Y

Y by Adventure10, Mango247

math-helli wrote:

who is the author of the problem?

Mr.jamali

Z K Y

The post below has been deleted. Click to close.

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

4 posts

#9 h Apr 10, 2018, 12:53 PM • 2 Y

Y by Adventure10, Mango247

easy problem

Attachments:

Z K Y

The post below has been deleted. Click to close.

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

50 posts

#10 h Feb 12, 2024, 1:39 AM

Y by

Abusing size and primes?

Let $P(x,y)$ denote the assertion $x+y|f(x)+f(y)$

Note $P(x,x)$ gives us $x|f(x)$

Now, consider all primes $p$ such that $p>>f(1),f(2)$

Since $f(p)\leq \frac{p^3}{2}$ , let $f(p)=ap^2+bp$ , where $a,b<p$

$P(p,1)$ gives us $p+1|f(p)+f(1)=ap^2+bp+f(1)$ $p+1|(b-a)p+f(1)$ since $p>>f(1)$ , this implies $b-a=f(1)$

Similarly, considering $P(p,2)$ gives us $b-2a=f(2)$

Equating the two, we get that $a=f(1)-f(2)$ $b=2f(1)-f(2)$ This also implies that for all $p>>f(1),f(2)$ , $f(p)=ap^2+bp$ for fixed constants $a,b$

Hence consider two large primes $p,q$
$P(p,q):$ $p+q|a(p^2+q^2)+b(p+q)$ $p+q|a(p^2+q^2)$ $p+q|2apq$ $p+q|2a$ But note $a\leq \frac{p}{2}$ which implies either $a=0$ or $p+q\leq p$

Hence, $a=0$ , which implies that $b=f(1)$

Now, for any arbitrary number $n$ , choose a prime $p$ such that $p>>f(n),f(1)$
$P(p,n):$
$p+n|f(1)p+f(n)$ which implies $f(n)=f(1) \cdot n$ $\forall n$ due to size

In order to satisfy the $x^3 \geq 2f(x)$ condition, all functions $f(n)=kn \forall n, \forall k \leq \lfloor \frac{(1395)^2}{2}\rfloor$ work

Q.E.D

This post has been edited 1 time. Last edited by Knty2006, Feb 12, 2024, 1:41 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a