Let $N$ be a positive integer and $A = a_1, a_2, ... , a_N$ be a sequence of real numbers. Define the sequence $f(A)$ to be $$f(A) = \left( \frac{a_1 + a_2}{2},\frac{a_2 + a_3}{2}, ...,\frac{a_{N-1} + a_N}{2},\frac{a_N + a_1}{2}\right)$$and for $k$ a positive integer define $f^k (A)$ to be$ f$ applied to $A$ consecutively $k$ times (i.e. $f(f(... f(A)))$) Find all sequences $A = (a_1, a_2,..., a_N)$ of integers such that $f^k (A)$ contains only integers for all $k$.
Problem
Source: Canada RepĂȘchage 2020/3 CMOQR
Tags: Sequence, algebra
25.04.2020 23:46
Consider the sequence $M_k=\max(f^k(A))$ and $m_k=\min(f^k(A))$ for integers $k \geq 0$ ($f^0(A) = A$). The sequence $(M_k)_k$ (resp. $(m_k)_k$) is decreasing (resp. increasing). Both of them are integer sequences. In addition, $M_k \geq m_k \geq m_0$ for any integer $k \geq 0$. Hence, $(M_k)_k$ is a decreasing sequence of integers bounded below. Therefore $(M_k)_k$ is eventually constant. Consider $n_0 \geq 0$ such that $M_k=M$ for all $k \geq n_0$. It is easy to see that if $\max(A)=\max(f(A))=s$ and $f(A)_i=s$, then $A_i=A_{i \pmod N + 1}=s$. $(1)$ Therefore we can take a large $n \geq Nn_0$ and $1 \leq i \leq N$ such that $f^n(A)_i=M$ (which exists since $M_n=M$), and apply (1) recursively to prove that there exist $i_0 \geq n_0$ such that $f^{i_0}(A)=M(1, ..., 1)$. - Case 1: $N$ odd. The matrix of the linear operator $f$, denoted $F$, is invertible ($\det(F)=\frac{1}{2^{N-1}}$) and satisfies $F(1, ..., 1)^t=(1, ..., 1)^t$, hence $F^{-1}(1, ..., 1)^t=(1, ..., 1)^t$. Therefore if $X \in \mathbb{R}^n$ satisfies $F X^t=M (1, ..., 1)^t$ then $X=M(1, ..., 1)^t$. Apply this to $f^{i_0}(A)$ to get $A=M(1, ..., 1)$. - Case 1: $N=2n$ even. The matrix $F$ in this case is not invertible. Notice that $f(A)=M(1, ..., 1)$ implies $a_{2i}=u$ for $1 \leq i \leq n$ and $a_{2i-1}=v$ for $1 \leq i \leq n$, where $u+v=2M$. Notice also that $f(A)=(u, v, ..., u, v)$, then $a_{2i}=a_2+(i-1)d$ and $a_{2i-1}=a_1-(i-1)d$ for $1 \leq i \leq n$, where $d=2(u-v)$. But $(n - 1) d = a_{2n}-a_2 = (a_{2n} + a_1) - (a_1 + a_2) = 2(v - u) = -d$, therefore $d=0$. Hence $A=u(1, ..., 1)$. This means that $2 \mid u -v $ and $f(A) = (u, v...,u, v)$ $\implies$ $A=(u',v', ...,u', v')$ for some integers $u', v'$ with the same parity. Starting from $f^{i_0}(A)=M(1, ..., 1)$ we can apply the previous process recursively to find two integers $u, v$ with the same parity such that $A=(u, v, ..., u, v)$. Conclusion: $N$ odd $\implies$ $A=M(1, ...,1)$ for some integer $M$. $N$ even $\implies$ $A=(u, v, ..., u, v)$ for some integers $u, v$ having the same parity.
26.04.2020 03:15
20.08.2020 18:25
Claim: There exists some integer $L$ such that $f^L(A) = \{c, c, c, \dots , c\}$ for some constant integer $c$. Proof: Let $M_k$ and $m_k$ denote the maximum and minimum elements respectively of the sequence $f^k(A)$. Let $a^k_i$ denote the $i$-th element of the sequence $f^k(A)$, where indices are taken $\pmod{n}$. Due to the recursive relation of the sequences, $$M_{k+1} = \dfrac{a^k_i+a^k_{i+1}}{2} \le \dfrac{M_k+M_k}{2} = M_k$$Similarly, we have that $m_{k+1} \ge m_k$. If $M_{k+1} = M_k$ holds for infinitely many $k$, that would imply that $M_k = m_k$ so the sequence $f^k(A)$ is constant, as desired. Thus if we have that $M_{k+1} = M_k$ holds for only finitely many $k$ the sequence $\{M_k\}$ is decreasing and bounded from below, so it must eventually be constant. A similar argument applies for $\{m_k\}$. Now it is relatively easy to start from the constant sequence $f^L(A) = \{c, c, \dots, c\}$ and work backwards. Case 1: $N$ is odd If $N$ is odd, we have that $ f^{L-1}(A) = \{e, f, e, \dots , e\}$ for integers $e, f$ such that $e+f = 2c$. But then $e+e = 2c$ so $e = c$ and $f=c$. Thus working backwards, we have that $\boxed{f(A) = f^{L-1}(A) = \{c, c, \dots, c\}}$. Case 2: $N$ is even If $N$ is even, we have that $ f^{L-1}(A) = \{e, f, e, \dots , f\}$ for integers $e, f$ such that $e+f = 2c$. WLOG, let $f \ge e$. Then we have $a^{L-2}_{2k}+a^{L-2}_{2k+1} = 2f \ge 2e = a^{L-2}_{2k+1} + a^{L-2}_{2k+2} \Rightarrow a^{L-2}_{2k} \ge a^{L-2}_{2k+2} \Rightarrow a^{L-2}_2 \ge a^{L-2}_N$. But we have $a^{L-2}_1+a^{L-2}_2 = 2e \le 2f = a^{L-2}_1+a^{L-2}_N \Rightarrow a^{L-2}_2 \le a^{L-2}_N$. So either $a^{L-2}_2 = a^{L-2}_N$ so $e=f=c$ or the sequence $f^{L-2}(A)$ does not exist. Then we must have that $\boxed{f(A) = \{e, f, e, \dots, f\}}$ where $e+f = 2c$ for some integer $c$.