Injective arithmetic comparison

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

Injective arithmetic comparison

G H J

Reveal topic tags

arithmetic sequence

L

G H BBookmark kLocked kLocked NReply

Source: Own .. probably own

The post below has been deleted. Click to close.

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

4657 posts

#1 h Jan 16, 2017, 3:41 AM • 4 Y

Y by Adventure10, Mango247, cubres, Pengu14

Show or refute :
For every injective function $f: \mathbb{N} \to \mathbb{N}$ there are elements $a,b,c$ in an arithmetic progression in the order $a<b<c$ such that $f(a)<f(b)<f(c)$ .

Z K Y

The post below has been deleted. Click to close.

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

919 posts

#2 h Apr 13, 2025, 11:08 AM

Y by

Let $a, b = a+\delta, c=a+2\delta$ (for $a,b,c,\delta \in \mathbb{N}$ ) form an arithmetic progression. If $f:\mathbb{N} \rightarrow \mathbb{N}$ is an injective function, then the following properties hold:

(1) For any distinct $\alpha,\beta \in \mathbb{N}$ , we have $f(\alpha) \neq f(\beta)$ (i.e. one-to-one).

(2) $f(n)$ is an increasing function such that $\alpha<\beta \Rightarrow f(\alpha)<f(\beta)$ .

Hence, $f(a) < f(b) < f(c)$ holds for any set of distinct positive integers $a<b<c$ that forms an arithmetic progression.

Z K Y

The post below has been deleted. Click to close.

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

11379 posts

#3 h Apr 13, 2025, 4:06 PM

Y by

Mathzeus1024 wrote:

If $f:\mathbb{N} \rightarrow \mathbb{N}$ is an injective function, then the following properties hold:
...
(2) $f(n)$ is an increasing function such that $\alpha<\beta \Rightarrow f(\alpha)<f(\beta)$ .

No.

This post has been edited 1 time. Last edited by jasperE3, Apr 13, 2025, 4:07 PM

Z K Y

The post below has been deleted. Click to close.

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

919 posts

#5 h Apr 15, 2025, 11:43 AM

Y by

jasperE3 wrote:

Mathzeus1024 wrote:

If $f:\mathbb{N} \rightarrow \mathbb{N}$ is an injective function, then the following properties hold:
...
(2) $f(n)$ is an increasing function such that $\alpha<\beta \Rightarrow f(\alpha)<f(\beta)$ .

No.

How so....unless $S = \{a,b,c\} \subset \mathbb{N}$ and we focus on only $f:S \rightarrow \mathbb{N}$ , which $f$ could be decreasing?

Z K Y

The post below has been deleted. Click to close.

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

2024 posts

#6 h Apr 15, 2025, 12:20 PM

Y by

Why would injectivitiy imply increasing? Take $f(x) = -x$ , for example.

Z K Y

The post below has been deleted. Click to close.

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

3789 posts

vsamc

#9 h Apr 15, 2025, 2:20 PM • 1 Y

Y by centslordm

Fix some $a$ . Then, there exists an $N$ such that $n\geq N \implies f(n) > f(a)$ due to injectivity. WLOG suppose $N > a$ . Now, I claim that there exists an $n\geq N$ such that $f(n) < f(m)$ for all $m > n$ . To show this, assume the contrary, Then, for any $n_0\geq N$ , there exists an $n_1 > n_0$ such that $f(n_0) > f(n_1)$ . Then there exists an $n_2 > n_1$ such that $f(n_1) > f(n_2)$ by the same logic, etc., so we have $f(n_0) > f(n_1) > f(n_2) > \cdots$ , impossible. So, there exists some $b\geq N$ such that $f(b) < f(m)$ for all $m > b$ . In particular, $f(b) < f(2b-a)$ . Furthermore, since $b\geq N > a$ , $a < b$ and $f(a) < f(b)$ . Thus, $a < b < 2b-a$ form an arithmetic sequence and $f(a) < f(b) < f(2b-a)$ , as desired.

Z K Y

The post below has been deleted. Click to close.

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

271 posts

#10 h Apr 15, 2025, 5:15 PM • 1 Y

Y by RobertRogo

adityaguharoy wrote:

Show or refute :
For every injective function $f: \mathbb{N} \to \mathbb{N}$ there are elements $a,b,c$ in an arithmetic progression in the order $a<b<c$ such that $f(a)<f(b)<f(c)$ .

We suppose for the sake of contradiction that no. Notice that as $f(1)$ is finite, there are finitely many $k$ so that $f(1) > f(k)$ . Therefore, for sufficiently large $k$ we have that $f(1) < f(k)$ , so by our assumption we require $f(k) > f(2k - 1)$ . But then pick such a $k$ , and note the chain
$f(k) > f(2k - 1) > f(4k - 3) > f(8k - 7) > \cdots$ contradicting the well ordering principle.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a