Let us call an integer sequence $\{ a_1,a_2, \dots \}$ nice if there exist a function $f: \mathbb{Z^+} \to \mathbb{Z^+} $ such that $$a_i \equiv a_j \pmod{n} \iff i\equiv j \pmod{f(n)}$$for all $i,j,n \in \mathbb{Z^+}$. Find all nice sequences.
Problem
Source: 2023 Turkey TST D3 P7
Tags: function, number theory
30.03.2023 00:11
30.03.2023 00:37
This one is pretty straightforward. It is obvious if $\{a_i \}$ works, then so does $\{a_i \} +c$, so assume that $a_1=0$ and $a_2=d$, for some integer $d$. If $d=0$, writing $j=2, i=1$ gives $f(n)=1$ for every positive integer $n$. Now taking $j=1$ gives $n|a_i$ for every $i, n$. Fixing $i$ and varying $n$ gives the constant solution $0, 0, \cdots$ where $ f \equiv 1$ satisfies. Take $d \neq 0$. Writing $i=2, j=1$ gives $n|d \Leftrightarrow f(n)|1 \Leftrightarrow f(n)=1$. Take $n|d, i=1$. RHS obviously holds, so does LHS $\Rightarrow d|a_j$ for all $j$s. We are now going to examine two seperate cases. $a_i$s are all different and otherwise. Assume all $a_i$s are different. We will prove $a_i=(i-1)d$ for $\forall i$ by induction over $i$. The result holds for $i=1, 2$. Assume it holds up to $i=k$ and let's try to prove it for $i=k+1$. Take $i=k+1$ and $j=k \Rightarrow n|a_{k+1}-a_k=a_{k+1}-(k-1)d \Leftrightarrow f(n)|1 \Leftrightarrow n|d$. This observation gives us $a_{k+1}-(k-1)d= \pm d$, so $a_{k+1}=kd$ or $a_{k+1}=(k-2)d$, however the latter case is impossible as all $a_i$s are different. So we are done and the only sequence here is $0, d, 2d, ...$ and $f(n)= \frac{n}{(n,d)}$ works obviously. Now take $k<l$ such that $a_k=a_l$. Taking $i=k$ and $j=l$ gives $f(n)|l-k$, thus $f$ is bounded and takes a value infinitely many times, call it $t$. Take $i=j+t, j=j$ and $n$ such that $f(n)=t$. RHS holds in this case and so does LHS, meaning that $n|a_{j+t}-a_j$. Since we can choose $n$ arbitrarily large $a_{j+t}=a_j$ for all $j$s, thus $\{ a_i \}$s are periodic. Choose minimal $i+1$ such that $a_{i+1}=a_1$. There do not exist equal $a_j$s among $a_1, a_2, \cdots a_i$, otherwise due to similar reasoning we just did we would have a smaller period, contradicting the fact of the choice of $i$. By the induction argument we can now show that $a_j=(j-1)d$ for $\forall 1 \leq j \leq i$. If $i \geq 3$, taking $i=i+1, j=1$ gives $f(n)|i$ for $\forall n$. Taking $i=i, j=1$ gives $n|a_i-a_1=(i-1)d \Leftrightarrow f(n)|i-1 \Leftrightarrow f(n)=1 \Leftrightarrow n|d$ which is an obvious contradiction. If $i=2$, we get the solution $0, d, 0, d, \cdots$ and $f(n)=1$ for $n|d$, $f(n)=2$ otherwise satisfies the conditions and we are done.
07.06.2023 06:22
Is turkey TST harder than IMO?
07.06.2023 07:32
No China TST is
09.06.2023 18:39
China TST is a little dirty :_:m well the problems are good but a little um.... sophisticated
12.10.2023 22:29
I hope it's correct. Assume that $a_{i+1} \neq a_i$ for one $i$. Since $a_{i+1} \equiv a_i \pmod{|a_{i+1}-a_i|}$, so $f(|a_{i+1}-a_i|)=1$. On the other hand; for all $j$, $a_{j+f(n)} \equiv a_j \pmod{n}$. From substituing $n=|a_{i+1}-a_i|$ at the second congurance, we obtain $(|a_{i+1}-a_i|)|a_{j+1}-a_j$. Let $S$ be the set of $|a_{i+1}-a_i|$ which are all different than $0$. Then for any two component of $S$ must be divide each other. Thus $S$ must be a set with only one component(i.e. $|a_{i+1}-a_i|$ must be constant). So we achieved a beautiful result. Result: If $a_n$ is a nice sequence, then either $a_n=a_{n+1}$ or $|a_{n+1}-a_n|$ equals to a constant. If $a_{n}=a_{n+1}$ for a positive integer $n$ , then $m|a_{n+1}-a_n$ for all $m$. So $f(m)=1$ for all $m$. Thus $m|a_i-a_j$ for all $m$. Since $m$ can be arbitrarily large, $a_n$ is constant.The function $f(n)=1$ holds for $a_n$ is constant. Let $|a_{n+1}-a_n|=c$. Then either $a_{n+1}=a_n+c$ or $a_{n+1}=a_n-c$ must hold. If there exists $n$ such that either $a_{n+1}=a_n+c$ and $a_{n+2}=a_{n+1}-c$ or $a_{n+1}=a_n-c$ and $a_{n+2}=a_{n+1}+c$ then $a_{n+2}=a_n$. Since $m|a_{n+2}-a_n$ for all $m$ we obtain $f(m)|2$ for all $m$. Thus $m|a_{n+2}-a_n$ for all $m$. Since $m$ can be arbitrarily large we obtain that $a_n$ is a sequence with period $2$. Let $a_{2n}=a$ and $a_{2n+1}=b$. For this situation the function $$f(n)=\begin{cases} 1 & \text{if }n|a-b \\ 2 & \text{otherwise} \end{cases} $$satisfies the conditions. If there does not exist an integer $n$ with above conditions than it's obvious that $a_n$ must be an arithmetic sequence. For this sequence if $d=a_{n+1}-a_n$ the function $f(n)= \frac{n}{gcd(n,|d|)}$ works. Thus we obtain that all nice sequences are sequences which are either arithmetic or constant or periodic with the period $2$.