Prueba sobre un combinatoric resultado

Question

Dado $x,y\in\{\pm 1\}^{100}$ tal que $\sum x_i =\sum y_i=0$, y un "adelante" operador $f\in S_{2n}$ tal que $f$ envía $1$ a $2$, $2$ a $3$,...,$2n-1$ a $2n$ y, finalmente,$2n$$1$, formando así un "bucle". Demostrar que existe una $k$ tal que $x$ $f^k(y):=(y_{f^k(1)},\cdots,y_{f^k(2n)})$ tiene al menos $50$ juego de las parejas, es decir, $\sum x_iy_{f^k(i)}\ge 0$.

Mis pensamientos eran, si esta hipótesis fuera verdadera, entonces no sería posible que $\sum x_if^k(y_i)<0$ todos los $k$. Resultó que este no es el camino correcto, lastimosamente. Entonces, ¿hay alguna alternativa que nos puede hacer？

Answer 1

Supongamos que por medio de la contradicción que $\sum_{i=1}^{100} x_i f^k(y_i) < 0$ todos los $k$, entonces también sería el caso de que $$\sum_{k=1}^{100}\left(\sum_{i=1}^{100} x_i f^k(y_i)\right) < 0.$$

Sin embargo, $$\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,$$

una contradicción. Por lo tanto $\sum_{i=1}^{100} x_i f^k(y_i) \geq 0$ debe mantener por lo menos un $k$.

Answer 2

Elija $1 \leq k \leq n$ uniformemente al azar y definir las variables aleatorias $Z_j = x_j y_{f^k(j)}$ todos los $j$$Z = \sum_{j = 1}^{2n} Z_j$. A continuación, por la linealidad de la expectativa de, $$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$.