NT Function with divisibility

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

NT Function with divisibility

G H J

Reveal topic tags

functional equation

L

G H BBookmark kLocked kLocked NReply

Source: Romanian District Olympiad 2023 9.4

The post below has been deleted. Click to close.

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

1742 posts

oVlad

#1 h Mar 11, 2023, 4:53 PM • 1 Y

Y by tiendung2006

Determine all strictly increasing functions $f:\mathbb{N}_0\to\mathbb{N}_0$ which satisfy $f(x)\cdot f(y)\mid (1+2x)\cdot f(y)+(1+2y)\cdot f(x)$ for all non-negative integers $x{}$ and $y{}$ .

Z K Y

The post below has been deleted. Click to close.

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

414 posts

#2 h Mar 11, 2023, 5:34 PM

Y by

$f(x) = 2x+1$ or $f(x) = 4x+2$ .

You can prove for primes $2a+1$ that $f(a) = 2a+1$ or $f(a) = 4a+2$ . Then use the strict increasing fact to show that in both cases we need every number between to primes to satisfy $f(b) = 2b+1$ or $f(b) = 4b+2$

Z K Y

The post below has been deleted. Click to close.

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

930 posts

#3 h Mar 19, 2024, 7:47 PM • 1 Y

Y by Mra123

Joy Bangla! The following proof is what @straight has pointed out.
The answer is $f(x)=2x+1$ and $f(x)=4x+2$ which can be easily verified.
Let $P(x,y)$ denote the given assertion.
Also consider $2<p_1<p_2< \cdots$ to be the infinite sequence of primes.
$P(0,0): f(0) \in \{1,2\}$ .
Case 1: $f(0)=1$
$P(x,0):f(x)|2x+1$
Thus $f \left(\frac{p_k-1}{2}\right)=p_k$ for all $k\in \mathbb{N}$ .
Also note that $P(x,0) \implies f(x)\text{ is odd}$ which in turn implies that $f(x+1) - f(x) \geq 2$ for all non negative integers $x$ .Next we have the following chain(for any $k\in \mathbb{N}$ ):
$p_k=\underbrace{f \left(\frac{p_k-1}{2}\right)<f \left(\frac{p_k+1}{2}\right)}_{\text{jump of length more than 1}}<\cdots < f \left(\frac{p_{k+1}-1}{2}\right)=p_{k+1}$ Thus all odd numbers between $p_k$ and $p_{k+1}$ are mapped with corresponding values of $f$ . Also $\mathbb{N} = \bigcup_{k\in \mathbb{N}} \left[\frac{p_k-1}{2},\frac{p_{k+1}-1}{2}\right]$ which shows that $f(x)=2x+1$ is true for all natural numbers $x$ .
Case 2: $f(0)=2$
Similar argument follows just like Case 1. $P(x,0): f(x)|4x+2$ and $2||f(x)$ . Thus we get that $f(x+1) - f(x) \geq 4$ for all non negative integers $x$ and $f \left(\frac{p_k-1}{2}\right)=2p_k$ for all $k\in \mathbb{N}$ .Next we have the following chain(for any $k\in \mathbb{N}$ ):
$2p_k=\underbrace{f \left(\frac{p_k-1}{2}\right)<f \left(\frac{p_k+1}{2}\right)}_{\text{jump of length more than 3}}<\cdots < f \left(\frac{p_{k+1}-1}{2}\right)=2p_{k+1}$ Thus all numbers $\equiv 2 \pmod 4$ between $2p_k$ and $2p_{k+1}$ are mapped with corresponding values of $f$ . Also $\mathbb{N} = \bigcup_{k\in \mathbb{N}} \left[\frac{p_k-1}{2},\frac{p_{k+1}-1}{2}\right]$ which shows that $f(x)=4x+2$ is true for all natural numbers $x$ .

This post has been edited 1 time. Last edited by sanyalarnab, Mar 19, 2024, 7:48 PM

Z K Y

The post below has been deleted. Click to close.

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

19 posts

#4 h Apr 10, 2025, 2:51 PM

Y by

arnab da orz

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a