f(n) - n is periodic

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

f(n) - n is periodic

G H J

Reveal topic tags

G H BBookmark kLocked kLocked NReply

Source: IMO 2015 Shortlist, N6

The post below has been deleted. Click to close.

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

62861

3564 posts

62861

#1 h Jul 7, 2016, 11:17 PM • 11 Y

Y by premchandj, anantmudgal09, MathbugAOPS, Kayak, Gaussian_cyber, k12byda5h, pablock, centslordm, Instance, basisthaamitkumar2, Adventure10

Let $\mathbb{Z}_{>0}$ denote the set of positive integers. Consider a function $f: \mathbb{Z}_{>0} \to \mathbb{Z}_{>0}$ . For any $m, n \in \mathbb{Z}_{>0}$ we write $f^n(m) = \underbrace{f(f(\ldots f}_{n}(m)\ldots))$ . Suppose that $f$ has the following two properties:

(i) if $m, n \in \mathbb{Z}_{>0}$ , then $\frac{f^n(m) - m}{n} \in \mathbb{Z}_{>0}$ ;
(ii) The set $\mathbb{Z}_{>0} \setminus \{f(n) \mid n\in \mathbb{Z}_{>0}\}$ is finite.

Prove that the sequence $f(1) - 1, f(2) - 2, f(3) - 3, \ldots$ is periodic.

Proposed by Ang Jie Jun, Singapore

This post has been edited 1 time. Last edited by 62861, Jul 20, 2016, 7:45 AM
Reason: added proposer

Z K Y

The post below has been deleted. Click to close.

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

62861

3564 posts

62861

#2 h Jul 7, 2016, 11:27 PM • 9 Y

Y by premchandj, Kayak, enzoP14, centslordm, Kobayashi, hakN, Adventure10, Mango247, MS_asdfgzxcvb

Solution

Z K Y

The post below has been deleted. Click to close.

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

fattypiggy123

615 posts

fattypiggy123

#3 h Jul 8, 2016, 4:11 AM • 7 Y

Y by mzy, 62861, DVDthe1st, premchandj, Cha21, centslordm, Adventure10

This problem was proposed by Ang Jie Jun from Singapore.

Z K Y

The post below has been deleted. Click to close.

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

Aiscrim

409 posts

Aiscrim

#6 h Jul 12, 2016, 2:18 PM • 4 Y

Y by premchandj, Kayak, Adventure10, Mango247

Keeping the same notations as CantonMathGuy, here is another proof for the fact that $(d_n)_{n\ge 0}$ is constant. Proof.
Comment.

Z K Y

The post below has been deleted. Click to close.

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

jjax

108 posts

jjax

#7 h Oct 17, 2016, 11:16 PM • 9 Y

Y by 62861, premchandj, anantmudgal09, v_Enhance, DVDthe1st, centslordm, Justpassingby, CyclicISLscelesTrapezoid, Adventure10

When I wrote this problem a long time ago I didn't realize there was theory related to it. I recently learned (at the Polya Problem Solving Seminar) that the structure of the solution set is something called a "disjoint covering system" https://en.wikipedia.org/wiki/Covering_system. You can do interesting math relating to this; for instance, your system must have repeated moduli.

Z K Y

The post below has been deleted. Click to close.

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

v_Enhance

6870 posts

v_Enhance

#8 h Feb 28, 2017, 3:22 PM • 7 Y

Y by nguyenhaan2209, aops29, v4913, mijail, centslordm, Adventure10, MS_asdfgzxcvb

First, we observe that $f$ is injective, since if $f(x) = f(y)$ then $n$ divides $f^n(x)-x$ and $f^n(y)-y$ for arbitrarily large $x$ and $y$ . This means that we can visualize $f$ as follows: if we let $x_1$ , $x_2$ , \dots, $x_h$ be the finitely many omitted elements in the range of $f$ , then we can construct a table $\begin{align*} x_1 &\to f(x_1) \to f^2(x_1) \to \dots \\ x_2 &\to f(x_2) \to f^2(x_2) \to \dots \\ &\vdots \\ x_h &\to f(x_h) \to f^2(x_h) \to \dots \end{align*}$ and we see that every positive integers appears exactly once in the table.

We claim that each row in the table is an arithmetic progression now. Notably, all such functions work; thus proving this claim will completely solve the problem.

Hence we define a chain to be a sequence $d_0 < d_1 < \dots < d_n$ of positive integers such that $|i-j|$ divides $|d_i - d_j|$ for $i \neq j$ . Thus rows of the table above form (infinite) chains. We will show that long chains must be arithmetic progressions:

Lemma: Let $p$ be a prime and let $d_0 < \dots < d_p$ be a chain for which $d_p = kp + d_0$ with $p > 3k$ . Then $d_i$ must be an arithmetic progression with common difference $k$ .
Proof. WLOG $d_0 = 0$ by shifting. We'll prove $d_i = ki$ for all $i$ in three steps.

First, suppose $k \le i \le p-k$ . Then $\begin{align*} d_i &\equiv 0 \pmod i \\ d_i &\equiv d_p = kp \pmod{p-i} \end{align*}$ and hence $d_i \equiv ki \pmod{i(p-i)}.$ Yet we also know $0 < d_i < kp$ . Now we check that $ki + i(p-i) \ge pk$ and $ki - i(p-i) \le 0$ for $k \le i \le p-k$ , so this forces $d_i = ki$ .
Next suppose $i = 1, \dots, k-1$ . Then $\begin{align*} d_i &\equiv d_{k+i} = k(k+i)\pmod{k} \\ d_i &\equiv d_{k+i+1} = k(k+i+1) \pmod{k+1} \end{align*}$ and hence $d_i \equiv ki \pmod{k(k+1)}$ . Since $0 < d_i < d_k = k^2$ , done.
The case $i > p-k$ is handled in the same way as above. $\blacksquare$

So all that suffices to do is apply the lemma to rows of the table. To do this, consider primes $p > 3h$ , and look at the $(h+1)$ st column of the table. Since every integer appears at least once in the table, some row must have an entry $\le hp + 1$ in this column. By pigeonhole on the rows, this must happen to some row infinitely many times; consequently that entire row is an arithmetic progression.

Then we can delete that row and apply a similar argument again. Repeating in this way we eventually find that all the rows are arithmetic progressions, as desired.

Z K Y

The post below has been deleted. Click to close.

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

MathStudent2002

934 posts

MathStudent2002

#9 h Feb 3, 2019, 8:55 PM • 5 Y

Y by hansu, centslordm, Kingsbane2139, Adventure10, bhan2025

Another arrow problem!

First we note that $f(m) > m$ for all $m$ from condition (i) with $n = 1$ . In particular, the directed graph on $\mathbb N = \mathbb Z_{>0}$ where $a\to b$ iff $f(a) = b$ is acyclic. Furthermore if $f(a) = f(b)$ , then $f^n(a) = f^n(b)$ for all $a,b$ , so $a\equiv b\pmod n$ for all $n$ , implying $a=b$ .

Now, we note that since our directed graph is cyclic, every node has indegree at most one and outdegree one, we get a bunch of chains with source nodes precisely the elements of $\mathbb N\setminus \{f(n)\colon n\in \mathbb N\}$ , which are finite. Furthermore, if $a_1 \to a_2\to \cdots$ are a chain, we have the property that $j-i\mid a_j-a_i$ for $i\neq j$ .

Now, define the density of a subset $S\subset \mathbb N$ by $\mu(S) = \lim_{n\to \infty} \frac{|S\cap [n]|}{n}$ if it exists (otherwise we will not speak of it). Furthermore, a set is said to be null if it has density zero and nontrivial otherwise. Note that if $\mu(S)$ does not exist, then $S$ is nontrivial.

First we do some bookwork and prove some facts about $\mu$ :

Lemma 1: Let $S_1,\ldots, S_n$ be null. Then, their union is null. In particular, if $S_1\cup\cdots \cup S_n$ is nontrivial, then one of the $S_i$ is nontrivial.

Proof: Indeed note that if $R = S_1\cup \cdots \cup S_n$ , $\frac{|R\cap [n]|}{n} \leq \sum \frac{|R\cap [n]|}{n},$ so taking the limit of both sides and noting that $\lim$ commutes with finite sums finishes. $\Box$

Lemma 2: If $S = \{x_1 < x_2 < \cdots\}$ , then if $\frac{n}{x_n}\to 0$ as $n\to \infty$ , we have $\mu(S) = 0$ .

Proof: Let $\varepsilon > 0$ . Pick $N$ such that for $n > N$ , $n < x_n\varepsilon$ . We claim that for $m > x_N$ , $|S\cap [m]| \leq m\varepsilon$ , which will finish. Indeed, let $x_\ell \leq m < x_{\ell+1}$ . Then, $|S\cap [m]| = \ell < x_\ell\varepsilon \leq m\varepsilon$ as desired. $\Box$

Lemma 3: Let $S = \{a+bn\colon n\in\mathbb N\}$ be an arithmetic progression. Then $S$ has density $\frac 1b$ .

Proof: Trivial from $\frac{|S\cap [n]|}{n} = \frac 1b + \frac{O(1)}{n}$ .

Lemma 4: Let $S_1,\ldots, S_n$ be disjoint arithmetic progressions with common differences $d_1,\ldots, d_n$ and total density $\sum \frac{1}{d_i} = 1$ . $\mathbb N \setminus \bigcup\limits_i S_i$ is finite.

Proof: Let $a_1,\ldots, a_n$ be the first terms of the sequences. Then, let $P = d_1\cdots d_n$ , and for any $a \geq \max(a_i)$ , $S_i$ contains exactly $\frac{P}{d_i}$ terms in the interval $[a+1,a+P]$ . In particular, since $S_i$ are disjoint, this means that all $\sum P{d_i} = P$ elements of the intervals are covered; in particular $a+1$ is covered, so any integer greater than $\max(a_i)$ lies in $\bigcup\limits_i S_i$ . $\Box$

Lemma 5: If $S$ has density zero, $\mathbb N \setminus S$ has density $1$ .

Proof: Let $R = \mathbb N \setminus S$ . We see that $\lim_{n\to\infty} \frac{|R\cap [n]|}{n} = \lim_{n\to\infty} \frac{n-|S\cap [n]|}{n} = 1-\lim_{n\to\infty} \frac{|S\cap[n]|}{n} = 1$ hence done. $\Box$

Now we arrive at the key lemma:

Lemma 6: Let $S = \{x_1 < x_2 < \cdots\}$ be nontrivial with $j-i\mid x_j-x_i$ . Let $d_i = x_{i+1}-x_i$ . Then, if $S$ is nontrivial, $d_i$ is constant (in particular bounded).

Proof: Note that $j-i\mid d_j-d_i$ as well.

First we show that $d_i$ is bounded. Let $d_m = \alpha$ be fixed. We claim that the number of indices $i$ such that $d_i < \alpha$ has density zero. Let $p > \alpha$ be a prime, then for $i = m+q$ for $p\mid q$ , we see that $d_i\equiv d_m\mod p$ , implying that $d_i \geq d_m$ since $d_m < p$ . So, if $d_i < \alpha$ , $|i-m|$ needs to be divisible only by primes less than or equal to $\alpha$ . Let $P$ be the set of such primes. Then, if $d_i<\alpha$ and $m < i \leq n$ , we must have $i-m = \prod\limits_{p_i\in P} p_i^{\alpha_i}$ . We further see that $\alpha_i < \log_{p_i} (n-m) + 1$ . So, if $Q$ is the set of $i$ with $d_i < p$ ,
$|S\cap [n]| < m + \prod_{p_i\in P}\log_{p_i}(n-m)+1 = o(n).$
So, by Lemma 5, the set of indices with $d_i \geq \alpha$ has density $1$ . Now say $d_i$ is unbounded. We will show that $\frac{n}{x_n}\to 0$ as $n\to \infty$ . Let $\varepsilon > 0$ . We will show that for sufficiently large $n$ , $n < x_n\varepsilon$ . Let $\alpha = \frac{2}{\varepsilon}$ . There exists $m$ with $d_m > \alpha$ , so the set of indices such that $d_i > \alpha$ has density one. In particular, there exists $N$ such that for $n > N$ , at least $0.99n$ of the indices in $i\in [n]$ satisfy $d_i > \alpha$ . In that case, for $n > N+1$ , we have that $x_n > d_1+\cdots+d_{n-1} > 0.99n\alpha,$ or $\varepsilon x_n > 1.98n > n$ as desired, since we contradict $S$ nontrivial by Lemma 2.

Thus, if the $d_i$ are unbounded then $S$ is null. Now, suppose $d_i$ is bounded above strictly by $\alpha$ , i.e. $\alpha > d_i$ for all $i$ . Suppose also that $d_i \neq d_j$ . Take distinct primes $p,q > \alpha > \max(d_i,d_j)$ . By CRT there must exist $k$ such that $k\equiv i\pmod p$ , $k\equiv j\pmod q$ . Then, $d_k\equiv d_i\pmod p$ , but $d_k < p$ so $d_k = d_i$ . However, we must then have $d_k\equiv d_j\pmod q$ , or $d_i\equiv d_j\pmod q$ , contradiction since $0 < d_i,d_j < q$ are distinct. This is a contradiction, so $d_i$ is constant. $\Box$

Now, we suppose $A_1,\ldots, A_k, B_1,\ldots, B_m$ are our chains formed by $f$ , so that $A_i$ are nontrivial and $B_i$ are null. Note that the $A_i$ must be arithmetic sequences by Lemma 6. On the other hand, $B = \cup B_i$ is null by Lemma 1, so Lemma 5 tells us that $A = \cup A_i$ has measure $1$ . But then Lemmas 3, 4 tell us that $B = \mathbb N \setminus A$ is finite. Since the chains are infinitely long, this means that $m = 0$ , i.e. the chains are all arithmetic progressions.

Now let $A_i$ be the arithmetic progression $\{a_i+nd_i\colon n\in \mathbb N\}$ . Let $D = \prod d_i$ . To solve the problem we will show that $f(n+D) - (n+D) = f(n)-n$ . Indeed, $n,n+D$ are in the same arithmetic progression $A_i$ , so $f(n+D)-(n+D) = a_i = f(n) -n$ and $f(n) - n$ has period $D$ . $\blacksquare$

This post has been edited 1 time. Last edited by MathStudent2002, Feb 3, 2019, 8:59 PM

Z K Y

The post below has been deleted. Click to close.

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

rmtf1111

698 posts

rmtf1111

#10 h Feb 12, 2019, 10:36 AM • 2 Y

Y by centslordm, Adventure10

Lemma. Let $g$ be an injective function that maps non-negative integers to integers bigger than a given $a$ . If for any $m,n \in \mathbb{Z}_{\ge 0}$ we have that $m-n \mid f(m)-f(n)$ and $f(0)=0$ then the set $\{f(n) \mid n\in \mathbb{Z}_{\ge0}\}$ has density non-zero only if $g$ is linear.
Proof: Note that $m\mid f(m)$ , so we can write $f(m)=k_mm$ . If $\{f(n) \mid n\in \mathbb{Z}_{\ge0}\}$ has density non-zero then there exists an infinite sequence $n_1, n_2, \dots$ such that $\mathcal{O}(k_{n_i})=1$ . Note that $n_i-n_j \mid g(n_i)-g(n_j)$ implies that $n_i-n_j \mid \gcd(n_i,n_j)(k_{n_i}-k_{n_j})$ , thus $k_{n_i}=k_{n_j}$ or $k_{n_i}\ge n_i/n_j-1+a$ , and by letting $i$ be arbitrarily big we see that $k_{n_i}$ is eventually constant. This means that for infinitely many $n$ we have that $g(n)=cn$ for a constant $c$ , thus $n-m \mid g(m)-cm$ for any $m$ and by letting $n\rightarrow \infty$ , we have that $g(n)=cn$ for any $n$ , implying the conclusion.

Back to the problem, it is easy to see that $f$ is injective. Let $S=\mathbb{Z}_{>0} \setminus \{f(n) \mid n\in \mathbb{Z}_{>0}\}=\{a_1,a_2, \cdots a_M\}$ and call the orbit of the number $n$ the set $O_n=\{n, f(n), f^2(n), \cdots \}$ . Note that for any $m$ we have that $f^l(m_{-l})=f^{l-1}(m_{-l+1})=\cdots f^1(m_{-1})=m$ for some $m_i$ 's, where $m_l \in \mathbb{Z}_{>0} \setminus \{f(n) \mid n\in \mathbb{Z}_{>0}\}$ , thus the orbits of $a_1, a_2, \cdots, a_M$ cover all positive integers. Letting $m=f^k(a)$ for some $a\in S$ we have that $n\mid f^{n+k}(a)-f^k(a)$ , so $g_a(n):=f^n(a)$ satisfies the conditions of the Lemma, thus $g_a$ is either linear or has density zero, this means that $O_a$ is either an arithmetic progression or a set with density zero. This holds true for any $a\in S$ , and because summing up the densities of all $O_{a_i}$ we must obtain $1$ , we have that each of the $O_{a_i}$ 's is an arithmetic sequence. Because any integer $n$ can be written as $f^k(a_i)$ for some $i$ , we have that the set $\{f(1) - 1, f(2) - 2, f(3) - 3, \cdots\}=\{d_1,d_2,\dots d_M\}$ where $g_{a_i}(n)=d_in$ , implying that the sequence $f(1) - 1, f(2) - 2, f(3) - 3, \cdots$ is periodic with period $D=d_1d_2\cdots d_M$ , because if $k\in O_{a_i}$ then $f(k)-k=d_i$ and $f(k+d_i)$ is also in $O_{a_i}$ , thus $f(k)-k=f(k+d_i)-(k+d_i)=f(f(k))-f(k)=d_i$ .

This post has been edited 3 times. Last edited by rmtf1111, Feb 12, 2019, 10:46 AM

Z K Y

The post below has been deleted. Click to close.

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

william122

1576 posts

william122

#11 h Apr 10, 2019, 11:49 AM • 3 Y

Y by centslordm, Adventure10, Mango247

Suppose $f(a)=f(b)$ . Then, $\frac{f^n(a)-a}{n}$ and $\frac{f^n(b)-b}{n}=\frac{f^n(a)-b}{n}$ are always integers. Therefore, their difference, $\frac{a-b}{n}$ , is also always integer, and we must have $a=b$ . This implies that $f$ is injective.

Now, consider the set of numbers $\{x_1,x_2,\ldots, x_k\}$ which are not part of the range of $f$ . For each $x_i$ , construct a chain $x_i,f(x_i),f^2(x_i),\ldots$ . Of course, these $k$ sequences have elements which are pairwise distinct, by injectivity. Furthermore, every positive integer occurs in one of these sequences, since we can always take $f^{-1}(f^{-1}(\ldots ((x))\ldots)$ , until we get to a number which doesn't have an inverse, and it therefore must be the start of a sequence. Finally, all such sequences must be increasing, since $f(m)-m>0$ for all $m$ .

We will now look at the sequence determined by $x_i$ . For simplicity, let these numbers be $y_1,y_2,\ldots$ . We have by (i) that $y_i\equiv y_{i+n}\pmod n\,\,\forall n$ . Now, consider the partial differences of $y_i$ , namely $y_2-y_1,y_3-y_2,\ldots$ . Also, suppose that this sequence is bounded, as we will deal with the unbounded case later.

First, it is easy to see that the partial differences are also periodic mod $n$ for all $n$ . Now, suppose there exists a number $N$ , such that the sequence $\{y_{i+1}-y_i\}\pmod N$ is nonconstant. Also, as the sequence is bounded, consider $y_{M+1}-y_M$ , which holds the largest value over all partial differences. Finally, take a number $R>>M$ , such that $\gcd(R,N)=1$ . If $y_{i+1}-y_i$ is different $\pmod N$ when $i\equiv i_1,i_2\pmod N$ . By Chinese Remainder Theorem, we can find numbers which are $i_1\pmod N$ and $M\pmod R$ , and $i_2\pmod N$ and $M\pmod R$ respectively. At the partial differences determined by these indices, both these numbers are at least $y_{M+1}-y_M$ , however they aren't the same $\pmod {NR}$ . Therefore, one of the partial differences at these two indices has value greater than $y_{M+1}-y_M$ , which is a contradiction to maximality.

What this means is that we cannot find such a mod $N$ , and $\{y_{i+1}-y_i\}$ is constant over all modulos, which immediately implies that the partial differences are constant.

So, if the partial differences of any of these $k$ sequences is bounded, then the sequence forms an arithmetic sequence. Now, consider all of the $k$ sequences which satisfy this property. Clearly, they cover all the integers if their densities sum to 1. On the other hand, if they sum to less than 1, then the rest of the numbers must be covered by the sequences with unbounded differences.

So, consider another sequence $z_1,z_2,\ldots$ , which has unbounded partial differences. Consider a certain partial difference $D=z_{i+1}-z_i$ . Now, for any $j>i+D$ , we must have $z_{j+1}-z_j\equiv z_{i+1}-z_i\equiv D\pmod {j-i}$ , so there exists a point in the sequence such that every partial difference is at least $D$ , and the density of $\{z_i\}$ is bounded at $\frac{1}{D}$ . However, as $D$ approaches infinity (we can do this because the differences are unbounded), this density approaches $0$ . So, all sequences with unbounded partial differences have density $0$ , and no finite amount of them can sum to a positive value.

Therefore, all of the $k$ sequences had to be arithmetic sequences. Considering $L$ , the $\text{lcm}$ of their respective differences, it is not hard to see that the sequence $\{f(i)-i\}$ is periodic in $L$ , 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.

yayups

1614 posts

yayups

#12 h Apr 11, 2019, 7:33 PM • 1 Y

Y by Adventure10

Claim 1: $f$ is injective.

Proof of Claim 1: Suppose $f(a)=f(b)$ . Thus, for all $n$ , we have
$a\equiv f^n(a)\equiv f^n(b)\equiv b\pmod{n},$ so by taking $n$ to be large, we see that $a=b$ , as desired. $\blacksquare$

We also note that $f(m)-m\in\mathbb{Z}_{>0}$ , so $f$ is increasing. Letting $R=\{r_1,\ldots,r_\ell\}=\mathbb{Z}_{>0} \setminus \{f(n) \mid n\in \mathbb{Z}_{>0}\}$ be the roots of $f$ , we see that we can think of $f$ as made up of increasing sequences
$r_i,f(r_i),f^2(r_i),\ldots$ that cover all of $\mathbb{Z}_{>0}$ with no overlaps and satisfying
$x-y\mid f^x(r_i)-f^y(r_i).$ We say that the root of a number $m$ is the $r_i$ of the sequence that it's part of. The key claim is all these sequences are arithmetic sequences. But to show this, we first need to show the consecutive differences are bounded.

Claim 2: There exists $D$ such that $f^{x+1}(r_i)-f^x(r_i)<D$ for all $x$ .

Proof of Claim 2: Suppose no such $D$ existed, so we have for arbitrarily large $M$ that there exists $x$ such that
$f^{x+1}(r_i)-f^x(r_i)=M.$ But then
$f^{x+L+1}(r_i)-f^{x+L}(r_i)\equiv M\pmod{L},$ so by taking $L=99M$ , we see that
$f^{y+1}(r_i)-f^y(r_i)>M$ for all $y>100M$ . Doing the same for each root, we see that for arbitrarily large $M$ , there exists some $\Lambda$ such that
$f^{y+1}(r_i)-f^y(r_i)>M$ for any $r_i$ and for any $y>\Lambda$ . This means that we have at most $100$ instances of the sequence rooted at $r_i$ in $[\Lambda,100\Lambda]$ , so we have a total of at most $100\ell\ll 99\Lambda$ numbers covered. But we need the sequences to together cover all numbers, so we have the desired contradiction. $\blacksquare$

For convenience, let $a_x=f^x(r_i)$ . Given that $x-y\mid a_x-a_y$ , and that the consecutive differences of $(a_x)$ are bounded, we'll show that $(a_x)$ is an arithmetic sequence. Pick some large $N$ . We see that
$\begin{align*} a_{N+1}&\equiv a_1\pmod{N} \\ a_{N+2}&\equiv a_2\pmod{N}. \end{align*}$ Thus, $a_{N+2}-a_{N+1}\equiv a_2-a_1\pmod{N}$ , but since $a_{N+2}-a_{N+1}<D$ , and since $N$ is sufficiently large, we see that
$a_{N+2}-a_{N+1}=a_2-a_1\equiv d.$ In a similar fashion, we derive that
$a_{N+k+1}=kd+a_{N+1}.$ But $a_{N+1}=a_1+gN$ , so in fact,
$a_{N+k+1}=a_1+gN+kd.$ But we see that
$a_{N+k+1}\equiv a_2=a_1+d\pmod{N+k-1},$ so $(k-1)d-g(k-1)\equiv 0\pmod{N+k-1}$ . Choose $k$ to be much larger than $g$ or $d$ so that $N+k-1$ is a prime. Then, we learn that $d\equiv g\pmod{N+k-1}$ , so we must have $d=g$ . Thus,
$a_{N+k}=a_1+(N+k)d,$ so the sequence is eventually arithmetic.

Finally, we show that this implies that the sequence is always arithmetic. We would like to show that $a_{p+1}=a_1+pd$ . Note that
$a_{p+1}\equiv a_1+(N+k)d\equiv a_1+pd\pmod{N+k-p}$ for arbitrarily large $k$ , so we have that $a_{p+1}=a_1+pd$ . Thus,
$f^x(r_i)=r_i+d_ix.$ So if a number $m$ has root $r_i$ , then $f(m)-m=d_i$ . Letting $\Delta=\mathrm{lcm}(d_1,\ldots,d_\ell)$ , we see that the root of $m$ and $m+\Delta$ are the same, so $f(m)-m=f(m+\Delta)-(m+\Delta)$ . Thus, $f(m)-m$ is periodic with period at most $\Delta$ , as desired. $\blacksquare$

This post has been edited 1 time. Last edited by yayups, Apr 11, 2019, 7:36 PM

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

#13 h Apr 29, 2020, 10:43 PM • 4 Y

Y by Mango247, Mango247, Mango247, SSS_123

Claim: $f$ is injective.

Proof: $f(a) = f(b) \implies k|f^k(a) - a, f^k(b) - b \implies k | a-b \forall k \in \mathbb N$ , hence $a=b$ .

Consider the graph obtained by drawing an arrow from $x$ to $y$ for each $(x,y) = (x,f(x))$ , the resulting graph is a union of finitely many disjoint chains and members of the chain are listed in ascending order ((i) additionally tells us that f(m) > m for all m). One of the chains must have positive density $d$ , thus a difference of $\le \frac{1}{d}$ between adjacent terms occurs infinitely many times. Suppose for some fixed $m$ , $j$ occurs infinitely many times as a quantity $f^n(m) - f^{n-1}(m)$ . Then $\forall k \in \mathbb N,$ $k\le n-2$
$\implies n-k| \begin{cases} f^n(m) - f^k(m),\\ f^{n-1}(m) - f^{k-1}(m) \end{cases}$ $\implies n-k | f^k(m) - f^{k-1}(m) - j$ . Taking $n\to \infty$ gives $f^k(m) = j + f^{k-1}(m) \forall k \in \mathbb N$ . Therefore if a chain has positive density then it must be an arithmetic progression, which forces all chains to have positive density (otherwise infinitely many elements of $\mathbb N$ will be left out). Now label the chains $1\sim t$ and label each number by the label of the chain containing the number, then the labeling must be periodic.

$\mathcal{YUH}.$

This post has been edited 1 time. Last edited by stroller, Apr 29, 2020, 10:44 PM

Z K Y

The post below has been deleted. Click to close.

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

TheUltimate123

1740 posts

TheUltimate123

#14 h Aug 29, 2020, 11:50 PM • 6 Y

Y by mijail, Mathematicsislovely, MatBoy-123, guptaamitu1, Ru83n05, hakN

Solved with eisirrational, goodbear, Th3Numb3rThr33.

It turns out that $f$ can be decomposed into finitely many infinite arithmetic sequences. We begin by exercising condition (i).

Claim: $f$ is increasing and injective.

Proof. By (i), $f(m)-m\ge1$ . If $f(a)=f(b)$ , then $a\equiv f^n(a)=f^n(b)\equiv b\pmod n$ for all $n$ , so $a=b$ . $\blacksquare$

Thus, we can decompose $f$ into chains of the form $m\to f(m)\to f^2(m)\to\cdots$ . We will now interpret condition (ii).

Claim: There are finitely many chains.

Proof. Note that $\mathbb N\setminus\{f(n):n\in\mathbb N\}$ contains the heads of all the chains, so there are only finitely many of them. $\blacksquare$

The key claim:

Claim: [USAMO 1995/4] Each chain is an arithmetic sequence or has density zero.

Proof. We know each chain is infinite and increasing. Let $q_0$ , $q_1$ , $\ldots$ be a chain, so by (i), $m-n$ divides $q_m-q_n$ for all $m$ , $n$ .

Let $Q$ be the linear polynomial with $Q(0)=q_0$ , $Q(1)=q_1$ . Scale everything up so that $Q$ has integer coefficients. Then $Q(n)\equiv Q(i)=q_i\equiv q_n\pmod{n-i}$ for $i=0,1$ , so by Chinese Remainder theorem $Q(n)\equiv q_n\pmod{n(n-1)}.$ Now,

If $Q(n)=q_n$ for infinitely many $n$ , then for all $m$ and $n$ with $Q(n)=q_n$ , we have $Q(m)\equiv Q(n)=q_n\equiv q_m\pmod{n-m}$ . By taking $n$ large, we have $Q(m)=q_m$ always, i.e.\ the chain is an arithmetic sequence.
Otherwise $q_n=Q(n)+kn(n-1)\ge O(n^2)$ for sufficiently large $n$ , so the chain has density zero.

$\blacksquare$

Now by Chinese Remainder theorem, the chains that are arithmetic sequences cover all integers larger than $N$ for some $N$ , so no chains of density 0 can exist. Therefore $f$ is comprised of arithmetic sequences, and the problem condition readily follows.

This post has been edited 1 time. Last edited by TheUltimate123, Aug 30, 2020, 3:13 AM

Z K Y

The post below has been deleted. Click to close.

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

Eyed

1065 posts

Eyed

#15 h Dec 28, 2020, 11:07 PM

Y by

The functions that satisfies these conditions can be constructed the following way: Split the set of natural numbers into finite arithmetic sequences. Then, for each $x$ , let $f(x)$ be the next number in it's arithmetic sequence. This works, since if $f(x) = x + c$ , then $f^{n}(x) - x = x+nc - x = nc$ , which satisfies the first condition. Furthermore, the only numbers not in the image of $f$ are the first terms of the arithmetic sequence, of which there are only finitely many.

Now we will prove that these are the only such functions that work. First, I claim that $f$ is injective. This is becuase if $f(a) = f(b)$ , then
$n | f^{n}(a) - a = f^{n}(b) - a, f^{n}(b) - b \Rightarrow n | a-b$ Take a large enough $n$ , which implies $a - b = 0$ and $a = b$ , so $f$ is injective. This means that if we place $f$ onto a graph of natural numbers, and connect $x$ and $f(x)$ with an arrow, it is a graph of chains. Furthermore, since only finite numbers are not in the image of $f$ , and every element at the beginning of each chain can not be in the image of $f$ , this means there are finite such chains.

I claim each chain is an arithmetic sequence. Assume that some chain was not; I claim for that chain to satisfy our problem condition, the difference between adjacent terms will be unbounded. If this was true, then it will lead to a contradiction, because for large enough terms, the function will be surjective, and if the difference between terms in a chain is unbounded, then it is impossible for every other chain to be an arithmetic sequence (or else some terms will be skipped, namely the ones that the non-arithmetic chain held). Thus, some other chain can not be an arithmetic sequence, so its differences are also unbounded. Using the same logic we can conclude that a third, a fourth, and so on number of chains aren't arithmetic sequences, which means the differences are all unbounded, thus infinitely many numbers are skipped, contradicting the problem condition. Thus, we need to prove that if a chain is not an arithmetic sequence, the difference between terms are unbounded.

We will prove this claim using contradiction. Assume, FTSOC, that the differences were bounded, such that every difference is less than some constant $C$ . Since the sequence is not an arithmetic sequence, there exists some term $x$ such that the next two terms are $x + m, x + n$ , and $n\neq 2m$ . Consider the $k+1$ th term, and let it be $x + r$ . Since the difference between terms is at most $C$ , we have $r \leq kC$ . Furthermore, we have $k | r, k-1 | r-m, k - 2 | r-n$ by the first condition. By CRT, we must have
$r\equiv 0\mod k, r\equiv m \mod k-1, r\equiv n\mod k-2 \Rightarrow r\equiv mk \mod k(k-1)$ Since $r\equiv n\mod k-2$ , we must have
$r\equiv tk(k-1) + mk \equiv n\mod k-2 \Rightarrow 2t + 2m\equiv n\mod k -2$ Since $2m\neq n$ , this means $t$ is positive, so
$r\equiv tk(k-1) + mk \mod k(k-1)(k-2) \Rightarrow r \geq tk(k-1) + mk \geq k(k-1)$ However, we also have $r\leq kC$ , so $k(k-1) \leq kC$ for all $k$ , which is clearly a contradiction for large enough $k$ .

This means every single chain is an arithmetic sequence. This implies all functions that satisfies these two conditions are the ones we constructed in the beginning.

Z K Y

The post below has been deleted. Click to close.

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

Supercali

1260 posts

Supercali

#16 h Dec 29, 2020, 9:20 AM

Y by

For storage:

We first claim that $f$ is injective. Indeed if $f(m_1)=f(m_2)$ , then by the first condition, $n \mid m_1-m_2$ for all $n$ , so $m_1=m_2$ .

Now let $c_1,c_2, \dots c_M$ be all the integers in $\mathbb{Z}_{>0} \setminus \{f(n) \mid n\in \mathbb{Z}_{>0}\}$ . Create a table with $M$ rows and infinitely many columns and fill $f^{j-1}(c_i)$ in cell $(i,j)$ . Then the table contains all positive integers exactly once, and by the first condition the numbers in any row are strictly increasing from left to right.

Call a set $S$ containing positive integers good if there exist finitely many arithmetic progressions $A_1,A_2, \dots A_l$ and a finite set $A_0$ such that $S = \bigcup\limits_{i=0}^l A_i$ .

Claim 1: Given a good set $S$ and an arithmetic progression $A$ , $S \setminus A$ is also good.
Proof: We can add all the small numbers in the finite set, and for the large numbers use Chinese Remainder theorem. $\blacksquare$

Claim 2: Suppose the numbers in some $m \leq M$ rows of the table together form a good set. Then at least one of the $m$ rows is an arithmetic progression.
Proof: WLOG the $m$ rows correspond to $c_1, \dots c_m$ . In the proof of this claim, whenever we refer to a "table", we are referring to only these $m$ rows. Let $S$ denote the corresponding good set.

Suppose for all $D$ and $i \leq m$ , $f^{n+1}(c_i)-f^n(c_i)>D$ holds for all sufficiently large $n$ . Consider some large $N,D$ (to be determined later) and look at the first $N$ columns of the table. Then the smallest number in $S$ that has not appeared yet must appear in the $(N+1)^{th}$ column. By our initial assumption, this number is at least $DN-p+1$ for some constant $p$ independent of $N$ . Let $k$ be the largest difference among all arithmetic progressions that form $S$ . Then it is easy to see that $S \cap [n] > \frac{n}{k}-q$ for some constant $q$ independent of $n$ $\implies$ there are at least $\frac{DN-p}{k}-q$ numbers in the first $N$ columns of the table. $\implies \ \frac{DN-p}{k}-q \leq mN$ Now choosing any $D > 1000mk$ and sufficiently large $N$ gives us a contradiction.

Therefore there exists a $d$ and an $i \leq m$ such that $f^{n+1}(c_i)-f^n(c_i)=d$ for infinitely many $n \geq 0$ . Choose any such large $n$ . Now for any $t \geq 0$ , we have $n-t \mid f^{n+1}(c_i)-f^{t+1}(c_i)$ and $n-t \mid f^{n}(c_i)-f^{t}(c_i)$ $\implies \ n-t \mid f^{t+1}(c_i)-f^t(c_i)-d$ Now taking large enough $n$ gives us $f^{t+1}(c_i)=f^t(c_i)+d$ which proves the claim. $\blacksquare$

Claim 1 and Claim 2 together prove that every row of the original table is an arithmetic progression. Let the differences be $d_1,d_2, \dots d_M$ . For any positive integer $n$ , let $g(n)$ denote the row to which $n$ belongs. Then $f(n)-n = d_{g(n)}$ ; therefore it is sufficient to prove that $g$ is periodic. Let $L=lcm (d_1,d_2, \dots d_M)$ ; then $g(n)$ is uniquely determined by residue of $n$ modulo $L$ . Therefore $g(a)=g(b)$ $\implies$ $g(a+1)=g(b+1)$ and so on, which proves periodicity of $g$ .

$\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

mathaddiction

308 posts

mathaddiction

#17 h Jan 18, 2021, 11:20 AM

Y by

CLAIM 1. $f$ is injective.
Proof.
Suppose $f(a)=f(b)$ , then for all $n$ we have $n|a-b$ , hence $a=b$ . $\blacksquare$

Now from condition (i) we have $f(n)>n$ . Therefore, suppose $\{a_1,a_2,...,a_n\}=\mathbb Z_{>0}\setminus\text{range }f$ .
Then the sets
$S_k=\{f^n(a_k):n\geq 0\}$ form a partition of $\mathbb Z$ . In particular, from condition (i), suppose $S_k=\{x_1,x_2,...\}$ where $x_1<x_2<...$ then
$a-b|x_a-x_b$ for any $a,b\in\mathbb Z$ .

CLAIM 2. Suppose an increasing function $g:\mathbb Z_{>0}\to \mathbb Z_{>0}$ satisfies
$a-b|g(a)-g(b)$ then $g$ is either a linear polynomial or $g(n+2)-g(n+1)\geq n+1$ for all sufficiently large $n$
Proof.
We call a number $n$ bad if $g(n+2)-g(n+1)\leq n$ . If $n$ is not bad for sufficiently large $n$ then we are done, otherwise suppose there exists sufficiently large bad $n$ .
Suppose $c=g(2)-g(1)$ , now notice that for all sufficiently large bad $n$ we have
$g(n+2)-g(2)\equiv g(n+1)-g(1)\pmod n$ Moreover, $|g(n+2)-g(2)-g(n+1)+g(1)|< n$
Hence $g(n+2)-g(2)=g(n+1)-g(1)$ which implies $g(n+2)-g(n+1)=c$ .
Now for each $a$ pick some bad $n$ such that $n+2-a$ is sufficiently large, then
$g(n+2)-g(a)\equiv g(n+1)-g(a-1)\equiv n+2-a\pmod n$ notice that $|g(n+2)-g(a)-g(n+1)+g(a-1)|\leq c+|g(a)-g(a-1)|$ , while $n+2-a$ is unbounded, hence L.H.S. must equal to zero. That is
$g(a)-g(a-1)=g(n+2)-g(n+1)=c$ as desired.
$\blacksquare$

Therefore from CLAIM 2, the sets $S_k$ either (i)form an arithmetic sequence or (ii) $x_{n+2}-x_{n+1}\geq n+1$ for all sufficiently large $n$ . Suppose $S_1,...,S_m$ are type (i) and $S_{m+1},...,S_k$ are type (ii).
Now notice that $A=\mathbb Z_{>0}\setminus(S_1\cup...\cup S_m)$ are either empty or either the union of some arithmetic sequence.
If it is nonempty, then the density of $A$ in $\mathbb Z_{>0}$ is of order $O(1)$ while the density of $S_{m+1}\cup...\cup S_k$ are of order at most $O(\frac{1}{n})$ , contradiction.
Hence all $S_1,...,S_k$ are arithmetic sequences, from which the conclusion easily follows(the l.c.m. of the common difference is a period).

This post has been edited 2 times. Last edited by mathaddiction, Jan 18, 2021, 11:26 AM

Z K Y

The post below has been deleted. Click to close.

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

pablock

168 posts

pablock

#18 h Jun 6, 2021, 11:16 PM

Y by

Apparently, I have a different solution. Anyway, what an amazing problem!!!

Fact 1: Let $x_1 < x_2 < \dots$ be an infinite sequence of positive integers such that $m-n \mid x_m-x_n$ for all $m,n \in \mathbb{N}$ . Suppose that for some $D$ , $x_m \le m \cdot D$ for infinitely many positive integers $m.$ Then $x_1, x_2, \dots$ is an arithmetic progression.
Proof: Let $m_1 < m_2 < \dots$ with $x_{m_i} \le Dm_i$ . Take any $k,l.$ Then for each $t$ big enough, $\frac{x_{m_t}-x_k}{m_t-k}$ is positive integer less than $2D$ . Hence by infinite Pigeonhole Principle, there is $d$ with $\frac{x_{m_t}-x_k}{m_t-k}=d \iff x_{m_t}=dm_t+x_k-dk$ for infinitely many values of $t.$ Now, we have $m_t-l \mid (dm_t+x_k-dk)-x_l \implies m_t-l \mid dl+x_k-dk-x_l$ for infinitely many values of $t$ , implying $x_l-dl=x_k-dk=b.$ $\Box$

Fact 2: Let positive integers $a_1, \dots, a_n, b_1, \dots, b_n$ be such that the sets $C_i=\{a_i+nb_i, n \in \mathbb{Z}_{\ge 0}\}$ are pairwise disjoint and there are infinitely many positive integers that don't belong to $C_1 \cup \dots \cup C_n$ . Then $\frac{1}{b_1}+ \dots+\frac{1}{b_n} < 1.$ Proof: Define $u_k$ as the number of positive integers less than or equal to $k$ that are not in $C_1 \cup \dots \cup C_n$ . Then notice that $K-u_K = \sum \bigg\lfloor \frac{K-a_i}{b_i} \bigg\rfloor \ge \sum \frac{K-a_i}{b_i}-1 = K \cdot \sum \frac{1}{b_i} - \bigg(\sum \frac{a_i}{b_i}+n \bigg)$ Taking $K$ big enough, $u_K > \sum \frac{a_i}{b_i}+n$ , implying $\sum \frac{1}{b_i} < 1.$ $\Box$

Lemma: Let
$\begin{align*} s_1=(x_{1,1}, x_{1,2}, x_{1,3}, \dots) \\ s_2=(x_{2,1}, x_{2,2}, x_{2,3}, \dots) \\ &\vdots \\ s_q=(x_{q,1}, x_{q,2}, x_{q,3}, \dots) \end{align*}$ be a partition of $\mathbb{N}$ into $q$ increasing, infinite sequences such that $m-n \mid x_{i,m}-x_{i,n}$ for all $i, m, n \in \mathbb{N}$ . Then each $s_i$ is an arithmetic progression.
Proof: The main idea is that some $s_i$ satisfies the condition of Fact 1. Indeed, for each $p$ , consider the minimum $x_{i,p}$ between $x_{1,p}, \dots, x_{q,p}$ . Because the sequences are increasing, all numbers less than $x_{i,p}$ must appear in a column less than $p$ , i.e., must be of the form $x_{j,k}$ with $k<p$ . Then we conclude that $x_{i,p}-1 \le (p-1) \cdot q.$ Now, by infinite PHP we have that for some $i$ , $x_{i,p} \le p \cdot q$ for infinitely many numbers $p.$ Using Fact 1, we conclude that some $s_i$ is an arithmetic progression.
Now we induct on the number $l$ of arithmetic progressions between $s_1, \dots, s_q.$
Take $\begin{align*} s_1=(x_{1,1}, x_{1,2}, x_{1,3}, \dots) \\ s_2=(x_{2,1}, x_{2,2}, x_{2,3}, \dots) \\ &\vdots \\ s_k=(x_{m,1}, x_{m,2}, x_{m,3}, \dots) \\ c_1=(a_1+nb_1)_{n \in \mathbb{Z}_{\ge 0}} \\ &\vdots \\ c_l=(a_l+nb_l)_{n \in \mathbb{Z}_{\ge 0}} \end{align*}$ We repeat the same argument: for each $p$ , consider the minimum $x_{i,p}$ between $x_{1,p}, \dots, x_{k,p}$ . Because the sequences are increasing, all numbers less than $x_{i,p}$ must either appear in a column less than $p$ in the $s_i$ 's, i.e., be of the form $x_{j,k}$ with $k<p$ or belong to a sequence $c_i$ .
Counting how many numbers less than $x_{i,p}$ appear in either the first $p-1$ columns of the $s_i$ 's or in the $c_i$ 's, we conclude that $x_{i,p}-1 \le (p-1) \cdot k + \sum_j \frac{x_{i,p}}{b_j}$ Using Fact 2, we have $\sum \frac{1}{b_j}<1$ then $x_{i,p} < p \cdot R$ for some fixed $R.$ Now, by infinite PHP we have that for some $i$ , $x_{i,p} \le p \cdot R$ for infinitely many numbers $p.$ Using Fact 1, we conclude that some $s_i$ is an arithmetic progression. $\Box$

We clearly have $f(m)>m$ and $f$ injective. Let $x_1, \dots, x_q$ be the numbers that are not in the image of $f$ . Consider
$\begin{align*} x_1 &\to f(x_1) \to f^2(x_1) \to \dots \\ x_2 &\to f(x_2) \to f^2(x_2) \to \dots \\ &\vdots \\ x_q &\to f(x_q) \to f^2(x_q) \to \dots \end{align*}$ such that every positive integer appears exactly once in the table (because every big number $K$ is $f(t(K))$ for some $t(K)<K$ , then we can decrease $t(t( \dots (K) \dots ))$ until we reach some $x_i$ .)
Then we can apply the Lemma. We get $f^n(x_i)=a_i+nb_i$ . Let $D = \prod b_i$ . It suffices to show that $f(n+D) - (n+D) = f(n)-n$ . Indeed, $n,n+D$ are in the same arithmetic progression $(a_i+nb_i)_{n \ge 0}$ , so $f(n+D)-(n+D) = b_i = f(n) -n$ and $f(n) - n$ has period $D.$ $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

Ru83n05

170 posts

Ru83n05

#19 h Apr 24, 2022, 5:19 PM

Y by

I'll sketch my solution for storage.

We begin by noticing the following two properties of $f$
Property 1: $f(m)>m$
Proof
Property 2: $f$ is injective
Proof

As $f(\mathbb{N})$ is cofinite, these two properties imply that we can partition $f(\mathbb{N})$ into a finite amount of (disjoint) orbits. The problem is equivalent to proving that these orbits are in fact arithmetic progressions, so once we show this we are done.

Call an orbit $\mathcal{O}$ bad if it has density $0$ and good otherwise.

Lemma: All good orbits are an arithmetic progression
Proof

Now I claim that there cannot be any bad orbits. Else let $D$ be the least common multiple of the differences of the arithmetic progressions. As all residues $\pmod D$ must eventually be covered, they will be covered by an arithmetic progression (An entire residue class cannot eventually be covered by bad orbits).
At the same time if we had any bad orbits, they eventually would intersect with an arithmetic progression, contradiction.

Thus we are done $\square$ .

Z K Y

The post below has been deleted. Click to close.

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

NoctNight

108 posts

NoctNight

#20 h Jun 5, 2022, 5:54 AM • 1 Y

Y by PRMOisTheHardestExam

Solution

Z K Y

The post below has been deleted. Click to close.

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

IAmTheHazard

5000 posts

IAmTheHazard

#21 h Jun 29, 2022, 3:10 PM

Y by

First note that if $f(a)=f(b)$ , then for all $n$ we have
$a \equiv f^n(a) \equiv f^n(b) \equiv b \pmod{n}$ for all $n$ , hence $a=b$ . Thus $f$ is injective. Further, we have $f^1(m)-m>0 \implies f(m)>m$ . If $a_1,\ldots,a_k$ are the elements not in $\{f(n) \mid n \in \mathbb{Z}_{>0}\}$ , then the two assertions above imply that the structure of $f$ when viewed as a directed graph in the obvious way is $k$ infinite chains, each starting with one of $a_1,\ldots,a_k$ .
The key claim is the following:

Claim: Any chain is either an arithmetic sequence, or has natural density $0$ .
Proof: Suppose our chain is $x_0 \to x_1 \to \cdots \to \cdots$ , so $i-j \mid x_i-x_j$ for all $i,j \geq 1$ . WLOG shift so that $x_0=0$ , which doesn't change the density in the naturals of the chain (we simply don't count $x_0$ in calculating the density). By putting $j=0$ , we have $i \mid x_i$ for all $i$ .
Now, suppose that there exists some natural number $a$ such that there are infinitely many $i$ with $x_i=ai$ . Then, if $x_j=bj$ for some $b$ , we have
$i-j \mid ai-bj \implies i-j \mid(a-b)j,$ but by picking $i$ sufficiently large we force $a=b$ , hence $x_i=ai$ for all $i$ , which means $x_0,x_1,\ldots$ is arithmetic.
Otherwise, by infinite pigeonhole, the set $\{\tfrac{x_i}{i} \mid i>0\}$ must be infinite, and every set of the form $\{i \mid \tfrac{x_i}{i}<C\}$ must be finite. Call an element of the chain $x_m$ cool if $x_m>x_{m-1},\ldots,x_0$ . Then,
$\sup_{i \geq n} \frac{|\{1,\ldots,i\} \cap \{x_1,x_2,\ldots\}|}{i}=\sup_{\substack{x_m \geq n\\x_m \text{ cool}}}\frac{|\{1,\ldots,x_m\} \cap \{x_1,x_2,\ldots\}|}{x_m}=\sup_{\substack{x_m \geq n\\x_m \text{ cool}}}\frac{m}{x_m}\leq \frac{1}{\inf_{x_m \geq n} \frac{x_m}{m}}.$ On the other hand, since every set of the form $\{i \mid \tfrac{x_i}{i}<C\}$ is finite, for every positive integer $C$ there exists some $n$ such that for all $x_m\geq n$ , we have $\tfrac{x_m}{m}\geq C$ , hence
$0=\frac{1}{\lim_{n \to \infty} \inf_{x_m\geq n}\tfrac{x_m}{m}} \geq \limsup_{n \to \infty} \frac{|\{1,\ldots,i\} \cap \{x_1,x_2,\ldots\}|}{i},$ so the upper density of the chain is actually $0$ , hence the density of the chain is also $0$ , concluding the proof of the claim.

Now note that if the union of all the chains with positive density is $S \neq \mathbb{N}$ , then the density of $\mathbb{N} \setminus S$ is positive. On the other hand, the union of finitely many sets with density $0$ has density $0$ itself, hence we must have $S=\mathbb{N}$ and thus no sets with density $0$ —that is, every chain is an arithmetic sequence. Thus by CRT we can label each chain from $1$ to $k$ and assign it a set of modulo- $N$ residues $R_k$ for some positive integer $N$ , such that each $R_k$ is pairwise disjoint, their union covers $\{0,\ldots,N-1\}$ , and the elements of chain $k$ are precisely those that are congruent to $r \pmod{N}$ for some $r \in R_k$ . Then it is clear that $f(1)-1,f(2)-2,\ldots$ is periodic with period $N$ , so we're done. $\blacksquare$

This post has been edited 1 time. Last edited by IAmTheHazard, Dec 28, 2022, 1:47 AM

Z K Y

The post below has been deleted. Click to close.

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

Inconsistent

1455 posts

Inconsistent

#22 h Aug 13, 2022, 12:20 PM • 2 Y

Y by Mango247, Mango247

After 2015 C5, missing this idea again is a crime!

First, take $n = \infty$ , then clearly since $f(a) = f(b) \Longrightarrow a \equiv b \pmod \infty$ , $f$ is injective. Furthermore, by $n = 1$ , $f$ is strictly increasing.

Therefore $f$ is a collection of chains, each of which starts with a number outside the range of the function. Thus $f$ is the union of a finite set of chains.

Now take any chain with nonzero asymptotic density $a, f(a), f^2(a), \ldots$ and let these be $g(0), g(1), \ldots$ respectively. The condition over the chain rewrites to $\frac{g(b)-g(a)}{b-a} \in \mathbb{Z}_{>0}$ for all $a, b \in \mathbb{Z}_{\geq 0}$ . Now consider this subproblem alone. By shifting $g(0)$ to $0$ and subtracting $(g(1)-g(0))x$ from the function $g$ , and it follows that $x \mid g(x)$ and $x-1 \mid g(x-1)$ for all $x$ . Thus $x(x-1) \mid g(x)$ , so for large $x$ , due to the monotonicity of $f$ , $g(x) = 0$ or $g(x) \geq x(x-1)$ for all sufficiently large $x$ , the latter of which contradicts the fact that $f$ has nonzero asymptotic density, hence $g$ must be linear, and its asymptotic density is the inverse of its slope.

Since there are finitely many such chains, we can now take the series modulo the lcm of the slopes of each chain, call it $s$ . It follows that since each chain does not intersect each other, the sum of their asymptotic densities must equal $1$ so for sufficiently large $x$ , every set of $s$ consecutive integers is partitioned entirely by the set of chains with nonzero asymptotic density, so since chains must be unbounded, every chain must have nonzero asymptotic density and be linear.

Now every chain is an arithmetic series, and if an arithmetic series does not extend as far back as possible, then if it is missing some term $x$ , $x$ must be part of a distinct chain, but then $x+s$ must be part of both chains, so by contradiction each arithmetic series extends as far back as possible. In other words, if a chain is dictated by $f(x) = x+d$ , then the first element of the chain is at most $d$ . Hence we can drop the sufficiently large condition and it is true that every set of $s$ consecutive integers is partitioned entirely by the set of chains with nonzero asymptotic density, most importantly periodically with period $s$ .

Now, since $f(x)-x$ is simply the slope of the chain that $x$ belongs to, it follows that the sequence of $f(x)-x$ is also periodic with period $s$ 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.

starchan

1602 posts

starchan

#23 h Oct 9, 2022, 8:56 AM

Y by

I'll infact describe all such functions. We begin with the digraph $G$ induced by $f$ . Note that $f$ is injective due to obvious reasons and loopless, thus $G$ is just a bunch of chains. From the second condition, there are finitely many chains. Call an increasing sequence $\{a_i\}_{\geqslant 1}$ hot if it satisfies $i-j \mid a_i-a_j$ for all $i > j>0$ . The main idea is that all hot sequences with nonzero density are infact just arithmetic progressions. First of all, if there exists a polynomial $f(n)$ with $\deg f > 1$ such that $a_i \geqslant f(i)$ for large enough $i$ then this sequence has zero density and thus we may choose $f \in \mathbb{Z}[x]$ such that $a_i < f(i)$ for all $i$ . From size restrictions and possibly USAMO 1995/4 we obtain then that $a_i = g(i)$ for some polynomial $g \in \mathbb{Q}[x]$ . At this point we again use density to conclude that $\deg g = 1$ and it follows that $a$ is an arithmetic progression. Suppose there are $k$ chains in $G$ with positive density. Each of these is an arithmetic progression, say with starting term $x_i$ and difference $d_i$ . Let $\mathcal S$ be the set of numbers not included among these chains. If $|\mathcal S| > 0$ then notice that infact $|\mathcal S| = \infty$ as every chain is infinite. Also this should have zero density. Consider the number of positive integers less than $N$ (large enough) in each chain. This is just $N/d_i + \mathcal O(1)$ and so overall we have $N + \mathcal O(1)$ numbers from the chains. Therefore we have $\mathcal O(1)$ numbers less than any large $N$ in $\mathcal S$ , as a result it is finite, contradiction. Therefore we must necessarily have $|\mathcal S| = 0$ and the function $f$ is described by these chains with values $x_i, d_i$ so that the formal identity $\sum_{i=1}^{k} \frac{b^{x_i}}{1-b^{d_i}} = \frac{1}{1-b}$ holds. Effectively these chains are arithmetic progressions that partition the set of natural numbers. At this point the $f(n)-n$ is periodic thing is more of an observation than something you prove.

This post has been edited 2 times. Last edited by starchan, Oct 9, 2022, 9:20 AM
Reason: u'll never know ahahaahahaahahahah

Z K Y

The post below has been deleted. Click to close.

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

Leo.Euler

577 posts

Leo.Euler

#25 h Aug 29, 2023, 1:18 AM

Y by

Let $G$ be the ``arrows graph" of $f$ , where we place a directed edge $n \rightarrow f(n)$ for each $n$ . A chain in $G$ is a sequence $n \rightarrow f(n) \rightarrow f^2(n) \rightarrow \dots$ for some $n$ not in the range of $f$ .

Claim: [basic properties] The following properties of $f$ hold:

$f(n) \ge n+1$ for all $n$ , and
$f$ is injective.

Proof. For part (a), noting that $f(m)-m$ is a positive integer by condition (i), we have $f(n) \ge n+1$ for all $n$ . For part (b), suppose that $f(a)=f(b)$ . It is clear that for all $n$ , $f^n(a)=f^n(b)$ . Thus, $n \mid f^n(a)-f^n(b) - (a-b)$ by (i), so all $n>0$ divide $a-b$ , implying that $a=b$ , and we are done.
:yoda:

By the first part of the prior claim, there are no cycles, and thus $G$ compromises of several disjoint chains. We claim that there are finitely many chains, but this is clear by condition (ii)! We characterize these chains in the following key claim.

Claim: Each chain is either an arithmetic sequence or has natural density zero.
Proof. Roughly speaking, we ``interpolate" the sequence using a linear polynomial. Consider the chain $a_0 \rightarrow a_1 \rightarrow \dots,$ and let $\ell(x)=a_0+(a_1-a_0)x$ . Then $\ell(n) \equiv a_0 \equiv a_n \pmod{n}$ and $\ell(n) \equiv a_1 \equiv a_n \pmod{n-1}$ . Therefore, by CRT, $\ell(n) \equiv a_n \pmod{n(n-1)}$ for all $n>1$ .

IIf $\ell(n) = a_n$ for only finitely many $n$ , then $a_n = \Omega(n^2)$ , which means that the chain has natural density zero. On the other hand, assume that $\ell(n)=a_n$ for infinitely many $n$ ; let $x$ be such an $n$ , and $y$ be any positive integer. Then $\ell(y) \equiv \ell(x) = a_x \equiv a_y \pmod{x-y}$ . Taking sufficiently large $x$ , $\ell(y) = a_y$ for all $y$ , which implies that the chain is an arithmetic sequence.
:yoda:

By CRT, the chains that are arithmetic sequences cover all but a finite number of positive integers; thus, none of the chains have natural density zero. Let the $\operatorname{lcm}$ of the common differences $d_i$ of the chains be $D$ . Inspecting the $i$ th chain, notice that $f(n) = n+d_i$ and $f(n+D) \equiv n+D+d_i.$ Subtracting the equalities yields $f(n+D)-(n+D)=f(n)-n$ , which implies that $f(m)-m$ is periodic with period dividing $D$ , and we conclude.
:starwars:

This post has been edited 1 time. Last edited by Leo.Euler, Sep 1, 2023, 6:00 PM

Z K Y

The post below has been deleted. Click to close.

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

YaoAOPS

1501 posts

YaoAOPS

#26 h Oct 15, 2023, 3:47 AM

Y by

If only all N6 were FE :sleep2:

.

Call an integer sequence $0 < a_1 < a_2 < \dots$ modular if $i - j \mid a_i - a_j$ . Call a sequence clear if its density in the integers approaches $0$ .

Claim: If a modular sequence has $a_n = a_{n+1}$ , then it must be clear.
Proof. WLOG let $n = 1$ by discarding earlier elements and let $a_1 = a_2 = 1$ by shifting. Then $a_{k+2} \ge k(k+1) + 1$ . $\blacksquare$

Claim: The only modular sequences that aren't clear are increasing arithmetic progressions.
Proof. Let $a_1, a_2, \dots$ be a non clear modular sequence. Consider the following operation: subtract $i$ from each $a_i$ , and discard the initial element, which may be $0$ . This only terminates when the entire sequence is $0$ .
This sequence remains modular as $a_n \ne a_{n+1}$ . Note that this decreases the difference between common elements by $1$ .
If we can do this operation infinitely many times, this implies that eventually the common difference becomes arbitrarily large, which implies clear, contradiction.
As such, this operation can be only done $N$ times, which implies that the common difference is $N$ eventually. Suppose that $a_M, a_{M+1}, \dots$ is an AP for some $M$ . However, the modular relation uniquely determines $a_{M-1}$ given this AP as also being in the AP. Repeating this gives all elements are in the AP. $\blacksquare$
Now, note that the graph on $f$ decomposes into finitely many chains that are modular. Each chain is either clear and has density $0$ , or is not and has density as an AP of $\frac{1}{n}$ for some integer $n$ .
However, summing density over all chains implies that the APs suffocate out the existence of clear modular chains.
As such, $f$ corresponds to a partition of ${\mathbb N}$ into APs, and maps elements along an AP.
The fact that $f(1) - 1, f(2) - 2, \dots$ is periodic follows by considering the least common multiple of all APs in a partition.

Z K Y

The post below has been deleted. Click to close.

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

atdaotlohbh

171 posts

atdaotlohbh

#27 h Jul 8, 2024, 8:37 PM

Y by

This problem can be easily solved after seeing the solution of that year's P6 (C5). I'm suprised two identical ideas happened to be sent in the same year to the shortlist
$n=1$ implies $f(m)>m$ . If $f(a)=f(b)$ , then $a-b \vdots n$ for all $n$ , and thus $a=b$ .
We will draw an arrow from $x$ to $f(x)$ . Consider all chains formed by the arrows. (ii) implies that there are finitely many of them.
Take any chain, say it is $a_1 \rightarrow a_2 \ldots$ . Let $d_i=a_{i+1}-a_i$ . Using (i) on $m,n=a_y,x-y$ and $a_{y+1},x-y$ we get that $d_x-d_y \vdots x-y$
We will divide all chains into two categories: stable when $d_i$ is const, and unstable otherwise
Consider any unstable chain, let $d_1 \neq d_x$ . Then for any huge $n$ : $d_{n+x}-d_x \vdots n$ and $d_{n+x}-d_1 \vdots n+x-1$ . Because $d_1 \neq d_x$ , $d_{n+x} \geq n$ . So from some moment this $d_i$ start getting super big
Now take any long enough list of consecutive numbers, where none of them is a member of an unstable chain (because it's jump is too big and overjumped the list by far). It is covered only with stable chains, which are arithmetic progressions. Because the list can be arbitrarily long, this arithmetic progressions actually cover all positive integers, but then there is no room for unstable chains, and so there are no unstable chains. Hence, we showed that all chains are arithmetic progressions
Now the lcm of all the common differences of our arithmetic progressions is the period of the sequence $f(i)-i$

Z K Y

The post below has been deleted. Click to close.

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

quantam13

108 posts

quantam13

#28 h Mar 31, 2025, 6:27 AM • 1 Y

Y by L13832

Firstly notice that $f$ is injective since if $f(x)=f(y)$ , we get $x\equiv f^n(x)=f^n(y)\equiv y\pmod n$ for all integers $n$ . We also have that $f(m)>m$ for every integer $m$ . Thus if $x_1, x_2, \dots ,x_k$ are the finitley many naturals that are not in the range of $f$ , the arrows graph of $f$ will look like the following:
$\begin{align*} x_1 &\to f(x_1) \to f^2(x_1) \to \dots \\ x_2 &\to f(x_2) \to f^2(x_2) \to \dots \\ &\vdots \\ x_k &\to f(x_k) \to f^2(x_k) \to \dots \end{align*}$ Every natural number will appear at some point and there will be no cycles in the table since every "chain" is increasing

Claim[USAMO 1995/4]: Every chain in the arrows graph is an arithmetic progression
Proof of claim: We know that each chain is infinite and increasing. If a chain is $a_1, a_2, a_3, \dots$ , we get that $a_i-a_j\mid i-j$ for all integers $i,j$ . Thus each chain is an arithmetic progression or has density zero by USAMO 1995/4. Since there are finite number of chains, there are finite number of chains with density zero and thus a non zero number of chains will be arithmetic progressions. Since the chains partition the integers, we can get that there are no chains of density zero, so every chain is an arithmetic progression $\square$ .

But after this, claim, its trivial to get the desired result.

Z K Y

N Quick Reply