Examining cycles in a sequence I am looking at a problem in Engel's problem solving strategies:

Start with an $n$-tuple $S=(a_0,a_1,\ldots, a_{n-1})$ of nonnegative integers.
Define the operation $T(S):=(|a_0-a_1|, |a_1-a_2|,\ldots, |a_{n-1}-a_0|)$.
Now consider the sequence $S, T(S), T(T(S)),\ldots$.
For instance, if we take $n=4$ and $S=(0,3,10,13)$, we get
$(0,3,10,13)\mapsto (3,7,3,13)\mapsto (4,4,10,10)\mapsto(0,6,0,6)\mapsto(6,6,6,6)\mapsto(0,0,0,0)$.

*

*Prove that, for $n\neq 2^r,$ we get (up to some exceptions) a cycle containing just two numbers: $0$, and evenly often some number $a>0$.


*Let $n\neq 2^r$ and let $c(n)$ be the cycle length. Prove that $c(2n)=2c(n)$ up to some exceptions.


*Prove that, for odd $n$, $S=(0,0,\ldots,0,1,1)$ always lies on a cycle.

The problem does not elaborate on what the 'exceptions' are.
Some given hints/progress I've made:

*

*The sequences $S$ and $tS$ have the same 'life expectancy', where $tS$ denotes multiplication of each element by $t\in \mathbb{N}$.
This is because $T(tS)=tT(S)$, so $T^k(tS)=0 \iff tT^k(S)=0 \iff T^k(S)=0$.


*For $n=2^r$, we always reach $(0,\ldots, 0)$.
Note that in mod 2, $|a-b|\equiv a+b$.
So $T(a_0,a_1,\ldots,a_{n-1})\equiv (a_0+a_1,a_1+a_2,\ldots,a_{n-1}+a_0)$, and $T^2(S)\equiv (a_0+a_2,a_1+a_3,\ldots)$ etc.
Continuing on, we see that these indices $a_i$ present in each slot has a structure identical to the parity of Pascal's triangle, where applying $T$ takes us to the next row in the triangle.
So for $n=2^r$, via the property of Pascal's triangle that the $2^r-1$'th row is entirely odd, we will reach $(\sum a_i, \sum a_i, \ldots, \sum a_i)$, which then maps to $(0, 0,\ldots,0)$ in mod 2.
Therefore after each $2^r$ steps we can extract a common factor of 2 from the $n$-tuple.
Further let $\max S$ denote the maximal element of $S$. Observing that $\max S\geq\max T(S)$, a descent argument will show that the eventually we must reach all $0$'s.


*A suggestion from the book: given the sequence $(a_0,a_1,\ldots,a_{n-1})$, assign the polynomial $p(x)=a_{n-1}+\ldots+a_0x^{n-1}$ with coefficients in mod 2, and $x^n=1$.
Then the polynomial $(1+x)p(x)$ belongs to $T(S)$.
EDIT:
the book includes a table of $c(n)$ values, which were computer generated. The first few values on the table are:
$c(3)=3, c(5)=15, c(7)=7, c(9)=63, c(11)=341, c(13)=819, c(15)=15, c(17)=255, c(19)=9709...$.
There seem to be various patterns in here, for instance, $c(2^k+1)=2^{2k}-1$.
 A: I shall provide an answer for the first and third problems in your question.
Before we dive into the solutions, let's get some notations out of the way. Call $S$ an $n$-sequence if the sequence is of the form $(a_1,...,a_n)$ and let $T^k(S)$ be the sequence obtained from applying the transformation $T$ to $S$, $k$-times. I use $(S)_i$ to denote the $i$-term of the sequence S i.e. $a_i$. I also use $\max(S)$ to denote $\max \{ (S)_i:1 \leq i \leq n \}$, the largest element in the sequence.
1. Prove that, for $n≠2^r$, we get (up to some exceptions) a cycle containing just two numbers: 0, and evenly often some number $a>0$.
Solution: I claim that if $S$ is an n-sequence that contains atleast $3$ distinct elements, then there exists a $k$ such that $\max(T^k(S)) < \max(S)$.
If we prove this claim, then we get that either $S$ gets reduced to the zero sequence or a sequence where the $\max(S)$ doesn't decrease and therefore contains two elements $\{0,a\}$, which is what is required to be shown. It is easy to show that $a$ then has to appear evenly often.
Proof of our claim: Let $a$ denote the smallest non-zero element in $S$ and let's say that $a=(S)_i$ for some $i$. Form the new sequence $S_0$ from $S$ in the following way: $$S_0 = ((S)_{i+1},...,(S)_n,(S)_1,...,(S)_i)$$
We have only cyclically moved the elements in $S$ to the right, so as to make $a$ the last element in our new sequence.
Note that applying $T$ to this new sequence $S_0$ yields a sequence that is just a cyclic rotation of our original $S$, so they share the same maximum element.
Claim: For $0 \leq k \leq n$, $(T^k(S_0))_{i} < \max(S)$ for all $i \geq n-k$.
We prove by strong induction on $k$.
Base Case:$(k=0)$
$T^k(S_0)=S_0$ and $a$ is the smallest non-zero element and is strictly smaller than $\max(S_0)$.
Induction Hypothesis: We assume that the claim is true for all $k\leq k_0<n$.
We need to prove that the claim is true for $k_0+1$.
$$(T^{k_0+1}(S))_i= \left|(T^{k_0}(S))_i - (T^{k_0}(S))_{i+1}\right|< \max(S)$$ for any $i\neq n-k_0-1, n$, from our induction hypothesis.
I'd like to show that $(T^{k_0+1}(S))_{n-k_0-1}< \max(S)$. The other case follows from a similar argument.
We know that
$$(T^{k_0+1}(S))_{n-k_0-1}= \left|(T^{k_0}(S))_{n-k_0-1} - (T^{k_0}(S))_{n-k_0}\right|.$$
If $(T^{k_0}(S))_{n-k_0}$ is non-zero, then
$$\left|(T^{k_0}(S))_{n-k_0-1} - (T^{k_0}(S))_{n-k_0}\right|< \max(S).$$
The problem occurs when
$$(T^{k_0}(S))_{n-k_0-1}= \max(S)$$
and $$(T^{k_0}(S))_{n-k_0}=0.$$
We are done if this is not possible. Suppose this were true, then
$$(T^{k_0}(S))_{n-k_0}=0=\left|(T^{k_0-1}(S))_{n-k_0} - (T^{k_0-1}(S))_{n-k_0+1}\right|$$
or
$$(T^{k_0-1}(S))_{n-k_0} = (T^{k_0-1}(S))_{n-k_0+1}.$$
If these terms were non-zero, then
$$(T^{k_0}(S))_{n-k_0-1}=\left|(T^{k_0-1}(S))_{n-k_0-1} - (T^{k_0-1}(S))_{n-k_0}\right|< \max(S),$$
which is not required. So, this forces
$$(T^{k_0-1}(S))_{n-k_0} = (T^{k_0-1}(S))_{n-k_0+1}=0$$ and
$$(T^{k_0-1}(S))_{n-k_0-1}=\max(S).$$
We repeat this argument to show that
$$(T^{k_0-j}(S))_{n-k_0} = ... = (T^{k_0-j}(S))_{n-k_0+j}=0$$
and
$$(T^{k_0-j}(S))_{n-k_0-1}=\max(S)$.$$
But this leads to a contradiction when $j=k_0$ because we have taken the last element of $S$ to be non-zero.}$
This concludes our induction.
From our claim, we see that if let $k=n$ then all the elements of $T^k(S)$ are lesser than
$\max(S)$, which was to be shown.
3. Prove that, for odd $n$, $S=(0,0,…,0,1,1)$ always lies on a cycle.
Solution: If $S$ doesn't lie in cycle, then it goes to $(0,...,0)$ eventually upon application of $T$. The only way to get to $(0,...,0)$ is if $T^k(S)=(1,...,1)$ for some $k$. That means that $T^k(S)$ contains an odd number of ones.
Claim: Let $S$ be a $n$-sequence ,for odd $n$, such that the elements of $S$ are $0$ or $1$. If $S$ contains even number of ones, then $T(S)$ contains even no. of ones.
Proof of our claim: We prove this by induction on $n$ where $n$ is odd.
Base Case:(n=3)
$S$ has to be $(0,1,1)$. $T(S)=(1,0,1)$. $T^2(S)=(1,1,0)$. $T^3(S)=S$. So, its true for $n=3$.
Induction hypothesis:
If $n$ is odd and $S$ is an $n$-sequence with even no. of ones, then $T(S)$ also has even no. of ones.
To prove: If $S$ is a $(n+2)$-sequence with even no. of ones, then $T(S)$ has even no. of ones.
In every $n+2$-sequence, there exists a pair $(a_i,a_{i+1})$ or $(a_n,a_1)$ such that $a_i=a_{i+1}$ or $a_1=a_n$ . WLOG, let's say that $a_i=a_{i+1}=0$.
Fix some such $i$. Create a new sequence $S_0=(a_{i+1},...,a_n,a_1,...,a_{i})$.
Now, The deleted sequence $S'_0=(a_{i+2},...,a_{i-1})$ formed by deleting the first and last element in $S_0$ is a $n$-sequence that satisfies our induction hypothesis.
$$T(S_0)=((S'_0)_1, (T(S'_0))_1,...,(T(S'_0))_{n-1},(S'_0)_n,0)$$
If the first $n-1$ elements of the deleted sequence already has even no. of ones, it means that $(S'_0)_1,(S'_0)_n$ are of same parity. If they were of different parity, then $(T(S'_0))_n=1$ which makes the overall no. of ones odd.
If the first $n-1$ elements of the deleted sequence has odd no. of ones, it means that $(S'_0)_1,(S'_0)_n$ are of different parity.
Either way, $T(S)$ has an even number of ones.
This concludes our induction and proves our claim.
From our claim, we see that $T^k(0,...,0,1,1)$ always has positive, even no. of ones and never becomes the zero sequence.
