Examining cycles in a sequence

Question

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)$.

1. 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$.

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

3. 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$.

Answer 1

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.

Answer 2

I will note some simple observations here:

1. As long as $S$ does not contain a $0$, $\max(T(S))<\max(S)$. Proof: $|a_i-a_{i+1}|<\max\{a_i,a_{i+1}\}\le \max(S)$

2. $T(S)$ will contain an even number of uneven elements. Proof: $$( a_1+a_2)+(a_2+a_3)+\cdots +(a_{n-1}+a_n)+(a_n+a_1)\\\equiv 2 (a_1+\cdots + a_n)\equiv 0 \pmod 2$$

3. If S contains only $0$ and $a>0$ then the number of $a$ in $T(S)$ must be even. Proof: $\frac 1 a S$ contains only $0$ and $1$. $a T(\frac 1 a S)$ is equal to $T(S)$ and the number of odd elements in $T(\frac 1 a S)$ is even as we stated before.

4. The cycle length depends not only on the length of the tuple but depend on its actual values:

Example:

iterate([0,0,1,0,0,1])
1 [0, 0, 1, 0, 0, 1]
2 [0, 1, 1, 0, 1, 1]
3 [1, 0, 1, 1, 0, 1]
4 [1, 1, 0, 1, 1, 0]
5 [0, 1, 1, 0, 1, 1]

cycle length = 3


iterate([0,0,1,0,1,1])
1 [0, 0, 1, 0, 1, 1]
2 [0, 1, 1, 1, 0, 1]
3 [1, 0, 0, 1, 1, 1]
4 [1, 0, 1, 0, 0, 0]
5 [1, 1, 1, 0, 0, 1]
6 [0, 0, 1, 0, 1, 0]
7 [0, 1, 1, 1, 1, 0]
8 [1, 0, 0, 0, 1, 0]
9 [1, 0, 0, 1, 1, 1]
10 [1, 0, 1, 0, 0, 0]
11 [1, 1, 1, 0, 0, 1]

cycle length = 6

---

Here is now the sketch of the proof for 1

I will demonstrate the simple idea using an example.

Assume that we start with the tuple

4  0  0  2  1 4  2  4  0  3

this tuple has the maximum value $4$ and at least on value different to $0$ and the maximum. Now we select a range that contains one of these values

4  0  0 <2 1> 4  2  4  0  3

Now we extend this range to the left and to the right before we reach $0$ or the maximum $4$. Our range has the following property:

1. it contains only values smaller than the maximum
2. its value most left is different to $0$ and the maximum
3. the value left to its most left value is $0$ or the maximum
4. its value most right value is different to $0$ and the maximum
5. the value right to its most right value is $0$ or the maximum

Now we apply the function 4 0 0 <2 1> 4 2 4 0 3 4 0 2 <1 3> 2 2 4 3 1

Now we again extend the range to the right and to the left and stop before we reach $0$ or the maximum $4$.

4  0  0 <2  1> 4  2  4  0  3
4  0 <2  1  3  2  2> 4  3  1  

The new range again has the 5 properties, these are the invariants. The new range will always be larger then the old range, because

1. the right index never decreases
2. the left index will be increased by at least 1

Both follows from the fact the $0<\left|a_i-a_{i+1}\right|<\max$, if one of $a_i,a_{i+1}$ is in $\{0,\max\}$ and the other is not in $\{0,\max\}$. To be more precise: if $l_1$ is the left index before the iteration and $r_1$ the right index before the iteration then we have:

• $a_{l_1} \in \{1,\ldots, \max-1\}$
• $a_{l_1-1} \in \{0, \max\}$
• $a_{r_1} \in \{1,\ldots, \max-1\}$
• $a_{r_1+1} \in \{0, \max\}$
• $a_i \in \{0,\ldots,\max-1\},\; \forall i: l_1\le i \le r_1$

After the iteration we have

$$T_{l_1-1}(S)=\left|a_{l_1-1}-a_{l_1} \right| \in \{1,\ldots,\max-1\}$$ $$T_{r_1}(S)=\left|a_{r_1}-a_{r_1+1} \right| \in \{1,\ldots,\max-1\}$$ $$T_{i}(S)=\left|a_{i}-a_{i+1} \right| \in \{0,\ldots,\max-1\}, \forall i: l_1\le i\lt r_1$$ and so we have the new left index $l_2 \le l_1-1$ and the new right index $r_2\ge r_1$

We must take care that the tuple must be view in a cyclic way, so we have to go "around the corner" when the left index reaches $1$ or the right index reaches $n-1$. So if we proceed we get

4  0  0 <2  1> 4  2  4  0  3
4  0 <2  1  3  2  2> 4  3  1  
4 <2  1  2  1  0  2  1  2  3>

and after the next step the maximum 4 vanished.

4  0  0 <2  1> 4  2  4  0  3
4  0 <2  1  3  2  2> 4  3  1  
4 <2  1  2  1  0  2  1  2  3>
2  1  1  1  1  2  1  1  1  1

Now we have a new maximum (2) and we can continue with the procedure. So after a finite number of steps we end either with $(0,0,\ldots,0)$ or with a tuple containing only $0$ and $a$.

We already showed in a previous part of this post that the number of position with values not $0$ must be even.