1

Suppose you have a list of truth values with $2^k$ elements for any natural number $k$. If the first element of this list is denoted as $L(1)$, then we can come up with a new list by performing the following operation $Q(L)$.

$Q(L)$:

temp:=$L(2^k)$

$L(2^k):=L(2^k)\oplus L(1)$

$L(n):=L(n)\oplus L(n+1),1\leq n<2^k-1$

$L(2^k-1):=L(2^k-1)\oplus temp$

Show that for all $k$, repeated iterations of the operator $Q$ onto $L$ results in the list consisting of only false values.

Example:

Original: $L=\{true,false,true,true\}$

After 1 iteration: $\{true,true,false,false\}$

After 2 iterations: $\{false,true,false,true\}$

After 3 iterations: $\{true,true,true,true\}$

After 4 iterations: $\{false,false,false,false\}$

I originally wanted to use induction for this, but it seems this system will break near the edges because of the looping around effect.

cmpen422help
  • 25
  • You might note that after one iteration you are reflecting the twos bit of $n-1$, then the second iteration you have the one bit of $n-1$ – Ross Millikan Feb 04 '15 at 03:21

1 Answers1

0

It seems the following.

For the convenience we assume that the lists are written around a circle, so the last element of the circle precedes the first. Farther, if we have two such circular lists $L$ and $L’$ then we can define a new circular list $L’’=L\oplus L’$ as elementwise XOR of $L$ and $L’$, that is $L’’(n)=L(n)\oplus L’(n)$ for each index $n$. As $0$ we denote the zero circular list, that is such a list $Z$ such that $Z(n)$ is false for each index $n$. Clearly, that $L\oplus L=0$ for each circular list $L$. Moreover, if $L$ is a circular list then by $dL$ we denote its circular shift, that is $dL(n)=L(n+1)$, if $1\le n\le 2^k$ and $dL(2^k)=L(1)$. We can easily check the distributivity of $\oplus$ and $d$, that is $d(L\oplus L’)= dL\oplus dL’$ for each circular lists $L$ and $L’$.

Now we can describe the operation $Q(L)$ as $Q(L)=L\oplus dL$ for each list $L$. Then $$Q^2(L)=Q(L\oplus dL)= (L\oplus dL)\oplus d(L\oplus dL)=L\oplus dL\oplus dL\oplus ddL=L\oplus d^2 L,$$ where $A^l(L)$ denotes a result of $l$ repeated iterations of an operation $A$ to the circular list $L$. Repeating the iterations, we similarly obtain $Q^{2^l}(L)=L\oplus d^{2^l}L$ for each natural $l$. In particular, $$Q^{2^k}(L)=L\oplus d^{2^k}L= L\oplus L=0.$$

Alex Ravsky
  • 90,434