Proof about a combinatoric result

Question

Given $x,y\in\{\pm 1\}^{100}$ such that $\sum x_i =\sum y_i=0$, and 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". Prove that there exists some $k$ such that $x$ and $f^k(y):=(y_{f^k(1)},\cdots,y_{f^k(2n)})$ has at least $50$ matching pairs, i.e., $\sum x_iy_{f^k(i)}\ge 0$.

My thoughts were, if this conjecture were true, then it wouldn't be possible that $\sum x_if^k(y_i)<0$ for all $k$. It turned out this isn't the right track, pitifully. So is there any alternative we can do？

Answer 1

Suppose by means of contradiction that $\sum_{i=1}^{100} x_i f^k(y_i) < 0$ for all $k$, then it would also be the case that $$\sum_{k=1}^{100}\left(\sum_{i=1}^{100} x_i f^k(y_i)\right) < 0.$$

However, $$\sum_{k=1}^{100}\left(\sum_{i=1}^{100} x_i f^k(y_i)\right)$$ $$ = \sum_{i=1}^{100}\left(\sum_{k=1}^{100} x_i f^k(y_i)\right)$$ $$ = \sum_{i=1}^{100}\left(x_i\sum_{k=1}^{100} f^k(y_i)\right)$$ $$ = \sum_{i=1}^{100}\left(x_i\sum_{k=1}^{100} y_i\right)$$ $$ = \sum_{i=1}^{100}\left(x_i \cdot 0\right) = 0,$$

a contradiction. Thus $\sum_{i=1}^{100} x_i f^k(y_i) \geq 0$ must hold for at least one $k$.

Answer 2

Choose $1 \leq k \leq n$ uniformly at random and define the random variables $Z_j = x_j y_{f^k(j)}$ for all $j$ and $Z = \sum_{j = 1}^{2n} Z_j$. Then by linearity of expectation, $$E[Z] = \sum_{j = 1}^{2n} E[Z_j] = 0$$ since the probability that $Z_j$ is $1$ is $1 / 2$. Since the expection is $0$ and is taken over $k$, there must be at least one choice of $k$ such that $\sum_{j = 1}^{2n} x_j y_{f^k(j)} \geq 0$.