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
cazanova19921
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.
BlazingMuddy
26.04.2020 03:15
$(x, x, \ldots, x)$ for any integer $x$, if $N$ is odd.
$(x, y, x, y, \ldots, x, y)$ for any integers $x$ and $y$ with the same parity, if $N$ is even.
For each sequence $A \in \mathbb{R}^N$ and for each $1 \leq i \leq N$, let $A_i$ be the $i$th entry of $A$.
Similar as above, we define $M_k = \max(f^k(A))$ for integers $k \geq 0$, and $m_0 = \min(A)$.
Furthermore, we define $T_k$ as the number of indices $i$ such that $f^k(A)_i = M_k$.
It is easy to see by small induction that $f^k(A)_i \geq m_0$ for all $k \geq 0$ and $1 \leq i \leq N$, so $M_k \geq m_0$ for all $k \geq 0$.
For the rest of the solution, we consider the indices modulo $N$.
Consider the sequence $(M_k, T_k)$ of two positive integers (For each $k \geq 0$, we have $1 \leq T_k \leq N$).
Let $S_k = M_k N + T_k$ for each $k \geq 0$.
It is easy to check that each $S_k$ is uniquely determined by $(M_k, T_k)$ for all $k \geq 0$.
Now, notice that for each $k \geq 0$ and any indices $i$, if either $f^k(A)_i < M_k$ or $f^k(A)_{i + 1} < M_k$, then $f^{k + 1}(A)_i < M_k$.
Thus, we can check that if $T_k < N$, then either $M_{k + 1} < M_k$ or $T_{k + 1} < T_k$.
Meanwhile, we can also check that if, $T_k = N$ then $f^k(A) = (M_k, M_k, \ldots, M_k)$ and thus $A_{k + 1} = A_k$.
Hence, the sequence $(S_k)_{k \geq 0}$ is strictly decreasing, either up to a point where $T_k = N$, and then becomes constant, or forever.
The latter is impossible since $S_k > M_k N \geq m_0 N$ for all $k \geq 0$, meaning that the sequence $(S_k)$ is bounded below.
Thus, there exists $K \geq 0$ and $M \in \mathbb{Z}$ such that $f^k(A) = (M, M, \ldots, M)$ for all $k \geq K$.
Now, suppose that $K$ is the smallest possible non-negative integer such that such $M$ exists.
We prove that either:
1. $K = 0$ and $A = (M, M, \ldots, M)$, or
2. $K = 1$, $N$ is even, and $A = (x, y, x, y, \ldots, x, y)$ for some integer $x \neq y$ with $x + y = 2M$.
Clearly, if $K = 0$, then $A = (M, M, \ldots, M)$, so now suppose that $K \geq 1$.
Consider the equation
\[ \frac{f^{K - 1}(A)_i + f^{K - 1}(A)_{i + 1}}{2} = f^K(A)_i = M \]for all $i \geq 1$.
It is easy to check that, for all $i \geq 1$,
\[ f^{K - 1}(A)_i = f^{K - 1}(A)_{i + 2} = 2M - f^{K - 1}(A)_{i + 1} \]If $N$ is odd, this would imply, by small induction, that $f^{K - 1}(A)_i = f^{K - 1}(A)_{i + N + 1} = f^{K - 1}(A)_{i + 1}$ and thus $f^{K - 1}(A)_i = M$ for all $i \geq 1$, contradicting the minimality of $K$.
Thus, $N$ is even, and $f^{K - 1}(A) = (x, y, x, y, \ldots, x, y)$ for some $x \neq y$ with $x + y = 2M$.
Now, suppose for the sake of contradiction that $K > 1$ (and thus $K \geq 2$).
Then, consider the equations:
\[ f^{K - 2}(A)_{2i - 1} + f^{K - 2}(A)_{2i} = x \]\[ f^{K - 2}(A)_{2i} + f^{K - 2}(A)_{2i + 1} = y \]for all $i \geq 1$.
Then, $f^{K - 2}(A)_{2i + 1} - f^{K - 2}(A)_{2i - 1} = y - x$ for all $i \geq 1$.
Hence,
\[ f^{K - 2}(A)_{N + 1} - f^{K - 2}(A)_1 = \sum_{i = 1}^{\frac{N}{2}} (f^{K - 2}(A)_{2i + 1} - f^{K - 2}(A)_{2i - 1}) = \frac{N}{2}(y - x) \]But the left hand side is $0$ while the right hand side is non-zero since $x \neq y$.
A contradiction.
Thus, if $K \geq 1$, then $K = 1$, $N$ is even, and $A = f^{K - 1}(A) = (x, y, x, y, \ldots, x, y)$ for some integer $x \neq y$ with $x + y = 2M$.
We are done.
peatlo17
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$.