Prove or disprove a combinatoric conjecture

55 Views Asked by At

We have a vector $x\in\Bbb \{\pm1\}^{2n}$, such that its component sum $\sum x_i=0$, meaning exactly half of $x$'s components are $+1$ and the other half $-1$. We also have a "forward" operator $f\in S_{2n}$ such that $f$ sends $1$ to $2$, $2$ to $3$,...,$2n-1$ to $2n$ and eventually $2n$ back to $1$, thus forming a "loop". I conjecture that there must exist some $k\in\Bbb N$ such that $$f^k(x):=(x_{f^k(1)},\cdots,x_{f^k(2n)})=-(x_1,\cdots,x_{2n})=-x.$$ I experimented some cases for $2n=4,6,8$ and was thus led to this conjecture. I don't have further idea to formulate a proof/disproof, though.

1

There are 1 best solutions below

3
On BEST ANSWER

The conjecture is false. For convenience, we will work with binary strings instead of vectors in ${\{\pm 1\}}^{2n}$. Now, if we index the elements of $x$ from zero instead of one, then $f(i) = i + 1 \bmod n$. Let us say that two indexes $0 \leq i, j < n$ are adjacent if $f(i) = j$ or $f(j) = i$. Then, for any $k$, it follows from the fact that $f^k(i) = i + k \bmod n$ that the indexes $i$ and $j$ are adjacent if and only if $f^k(i)$ and $f^k(j)$ are adjacent.

For a counter example, let $n = 6$ and consider the binary string $x = 010011$. By the above argument, for any $k$, $f^k(x)$ preserves adjacent elements, so if $f^k(x) = 101100$, then we must have $f^k(4) = 2$. This implies that $f^k(i) = i - 2 \bmod 6 = i + 4 \bmod 6$. However, then $f^k(x) = 001101 \not= 101100$.