For an $n$-tuple of integers, define a transformation to be: $$(a_1,a_2,\cdots,a_{n-1},a_n)\rightarrow (a_1+a_2, a_2+a_3, \cdots, a_{n-1}+a_n, a_n+a_1)$$ Find all ordered pairs of integers $(n,k)$ with $n,k\geq 2$, such that for any $n$-tuple of integers $(a_1,a_2,\cdots,a_{n-1},a_n)$, after a finite number of transformations, every element in the of the $n$-tuple is a multiple of $k$.
Problem
Source: CWMI 2016
Tags: number theory
20.08.2016 04:06
20.08.2016 06:46
Notice that you can't pick your $a_i$, the ordered pair $(n,k)$ must work for any arbitrary integral $n$-tuple.
20.08.2016 06:51
YanYau wrote: Notice that you can't pick your $a_i$, the ordered pair $(n,k)$ musty work for any arbitrary integral $n$-tuple. I think we can, because it works for any arbitrary $n$-tuple of integers $(a_1,a_2, \cdots , a_n)$.
20.08.2016 06:55
Ah okay I misread your proof, but there is still a flaw somewhere because $n$ can't be all natural numbers greater than 2. E.g. try $n=3$
20.08.2016 13:46
You are right, YanYau. I only show that $k=2^l$ in the above proof. Let me finish my solution: We will prove that $n=2^h$ is the only answer. Now, we denote that $a_b=a_{b \pmod{n}}$ if $b>n$. Claim. After some transformations, we will obtain a new $n$-tuple $(b_1,b_2, \cdots , b_n)$ such that $b_i \equiv \sum_{j=i}^{2^l+i-1}a_j \pmod{2}$ for all $1 \le i \le n$ for any $l \in \mathbb{N}$ or $(c_1,c_2, \cdots , c_n)$ such that $c_i \equiv a_i+a_{2^l+i} \pmod{2}$. Proof. We induct on $l$. For $l=1$ it's true. If it's true till $n=h$, which means we can obtain new $n$-tuple $(b_1,b_2, \cdots , b_n)$ such that $b_i \equiv \sum_{j=i}^{2^h+i-1}a_j \pmod{2}$. According to inductive hypothesis, we can obtain a new $n$-tuple $(c_1,c_2, \cdots , c_n)$ such that $c_i \equiv b_i + b_{2^h+i} \pmod{2}$. This follows $c_i \equiv \sum_{i=1}^{2^{h+1}+i-1}a_i \pmod{2}$. And we have $(c_1+c_2, c_2+c_3, \cdots , c_n+c_1) \equiv \left( a_1+a_{2^{h+1}+1}, \cdots , a_n+a_{2^{h+1}+n} \right) \pmod{2}$. We are done. $\square$ Back to the problem, if there exists odd prime factor $p$ of $n$ then we for $2^{h}<n<2^{h+1}$, we pick $a_i$ such that $2 \nmid a_1+a_2+ \cdots + a_{2^h}$ and $2 \mid a_2+a_3+ \cdots + a_{2^h+1}$. Note that if $n=2^a \cdot b$ with $2 \nmid b$ then $2^{h+ \varphi(b)m} \equiv 2^h \pmod{n}$ for any $m \in \mathbb{N}$. According to the claim, for any $m$, we can always obtain $(b_1,b_2, \cdots , b_n)$ such that $b_i \equiv \sum_{j=i}^{2^{h+\varphi(b)m}+j-1}a_j \pmod{2}$. We find that $$b_1 \equiv \sum_{j=1}^{2^{h+\varphi(b)m}}a_j \equiv \sum_{j=1}^{2^h}a_i+ K\sum_{i=1}^n a_i \pmod{2}.$$And $$b_2 \equiv \sum_{j=2}^{2^{h+\varphi(b)m}+1}a_j \equiv \sum_{j=2}^{2^h+1}+K\sum_{i=1}^na_i \pmod{2},$$where $K= \frac{2^{h+\varphi(b)m}-2^h}{n}$. Thus, after some transformations, we always find $b_0 \not\equiv b_1 \pmod{2}$, which gives a contradiction since $k=2^l$. Hence, $n=2^m$ for some $m \in \mathbb{N}$. Indeed, according to the lemma, after some transformation, we will find a new $n$-tuple $(b_1,b_2, \cdots , b_n)$ such that $b_1 \equiv b_2 \equiv \cdots \equiv b_n \equiv \sum_{i=1}^na_i \pmod{2}$. This means we can reach a stage where all numbers in $n$-tuple are all even. We apply the same method so that to get all numbers divisible by $k=2^l$. Thus, $(n,k)=(2^m,2^l)$ for any $m,l \in \mathbb{N}$.
28.01.2017 14:17
any orther better solutions?
01.11.2021 19:13
YanYau wrote: For an $n$-tuple of integers, define a transformation to be: $$(a_1,a_2,\cdots,a_{n-1},a_n)\rightarrow (a_1+a_2, a_2+a_3, \cdots, a_{n-1}+a_n, a_n+a_1)$$ Find all ordered pairs of integers $(n,k)$ with $n,k\geq 2$, such that for any $n$-tuple of integers $(a_1,a_2,\cdots,a_{n-1},a_n)$, after a finite number of transformations, every element in the of the $n$-tuple is a multiple of $k$. The answer is $\boxed{(n,k)=(2,k)}$ First of we claim that we can't have $k \ge 3$. Denote $f_n$ as the finonnacci numbers and $\delta(n)$ as the set at the $k$th transformation. Note that $$\delta(n)=\{f_n a_1+f_{n-1} \sum_{j=2}^n a_j,...............,f_n a_n+f_{n-1} \sum_{j= 1}^{n-1} a_j \}$$This implies that $n|f_n \left(a_n-a_{n-1} \right)-f_{n-1} \left(a_{n-1}-a_{n-2} \right)$ clearly this is invariant;it doesn't change.(it changes but it's change can be controlled) To show that for $n=2$ any $k$ works we notice that $$(a_1,a_2) \to (a_1+a_2,a_1+a_2) \to .................. \to (k(a_1+a_2),k(a_1+a_2))$$,hence we are done.$\blacksquare$
26.07.2023 14:55