1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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$ $\endgroup$ Commented Feb 4, 2015 at 3:21

1 Answer 1

0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .