Given a sequence $a_n$: \[ 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, \dots \](one '1', two '2' and so on) and another sequence $b_n$ such that $a_{b_n}=b_{a_n}$ for all positive integers $n$. It is known that $b_k=1$ for some $k>100$. Prove that $b_m=1$ for all $m>k$.
Problem
Source: Saint Petersburg olympiad 2024, 11.2
Tags: algebra, sequenses
nchuong1312
23.09.2024 17:51
NO_SQUARES wrote: Given a sequence $a_n$: \[ 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, \dots \](one '1', two '2' and so on) and another sequence $b_n$ such that $a_{b_n}=b_{a_n} (1)$ for all positive integers $n$. It is known that $b_k=1$ for some $k>100$. Prove that $b_m=1$ for all $m>k$.
Consider the sequence $(c_n)_{n \ge 1}: c_1 = k, c_{n+1} = a_{c_n}, \forall n =1,2,...$.
It is known that $a_n = \lfloor \sqrt{2n} + \frac{1}{2} \rfloor, \forall n$ so $a_n < n, \forall n >2$.
We infer $c_{n+1} < c_n, \forall n$, but $c_n \in \mathbb{N^*} \forall n$ so the $c_m = c, \forall m > N$ with N is a large enough number.
If $c > 2$ then $c_{m + 1} = a_{c_m} < c_m = c$ (contradict with c_{m+1} = c_m).
If $c = 1$ then by backward induction, $c_{n+1} = a_{c_n} = 1 \Rightarrow c_n = 1 \Rightarrow k = c_1 = 1$ (contradict with $k > 100$).
So $c$ must be $2$. We will prove $b_{c_n} = 1, \forall n = 1, 2, ...$ by induction.
We have $b_{c_1} = b_k = 1$ so the statement true with $n = 1$.
Assume that $b_{c_k} = 1$, replace $n$ in $(1)$ with $c_k$, we get $b_{c_{k+1}} = 1$.
Therefore, $b_2 = 1$. We will prove $b_m = 1, \forall m \in \left[1 + 2 + ... + (n-1) + 1; 1 + 2 + ... + n\right], \forall n \in \mathbb{N^*}$.
We have $b_2 = 1$ and $b_3 = 1$. Assume that this statement true for all $n \le k$ ($k \in \mathbb{N^*}$), we infer $b_m = 1, \forall 2 \le m \le (1 + 2 + ... + k)$.
Let $x$ be an arbitrary number in $[(1 + 2 + ... + k) + 1; (1 + 2 + ... + (k+1))]$. In $(1)$, let $n = x \Rightarrow a_{b_x} = b_{a_x} = 1$ ($a_x < (1 + 2 + ... + k)$) $\Rightarrow b_x = 1$.
By induction $b_m = 1, \forall m \in \left[1 + 2 + ... + (n-1) + 1; 1 + 2 + ... + n\right], \forall n \in \mathbb{N^*} \Rightarrow b_m = 1, \forall m \ge 2 \Rightarrow b_m = 1, \forall m > k$.