Elección de la mitad de prefijo y sufijo

Question

Considere dos listas: $(1,2,\dots,n)$$(a_1,a_2,\dots,a_n)$, donde el segundo de la lista es una permutación de la primera. ¿Existe un constante $c$ tal que para cualquier $n$ y para el segundo de la lista, se puede elegir un subconjunto $A\subseteq\{1,2,\dots,n\}$ del tamaño en la mayoría de los $n/2+c$, de modo que para cualquier prefijo y sufijo de la lista de cualquier longitud $k\in[1,n]$, al menos $k/2$ de los elementos son en $A$?

El $n/2$ es necesario que: incluso si sólo tenemos la lista de $(1,2,\dots,n)$ y requieren de la condición en el prefijo, la hora de tomar $k=n$ tenemos ya necesidad de incluir, al menos, $n/2$ elementos. Si sólo queremos los prefijos y sufijos de la primera lista, podemos optar $A=\{1,3,5,\dots\}$ a lo largo de con $n$ (si no está ya incluido), la que viene en la mayoría de las $n/2+1$ elementos.

Answer 1

Este problema puede reformularse como "Dada una permutación $\sigma$$\{1,\dots,n\}$, es siempre posible elegir $a_j=\pm 1$ de manera tal que todas las sumas parciales $\sum_{j=1}^k a_j$ $\sum_{j=1}^k a_{\sigma(j)}$ están delimitadas por una constante $C$". La respuesta es "Sí". Considere la gráfica en el que los vértices son $1,\dots,n$ y los bordes son de $1-2,3-4,5-6,\dots$ (blanco) y $\sigma(1)-\sigma(2), \sigma(3)-\sigma(4),\dots$ (amarillo). Si logramos elegir los signos, de modo que cada arista conecta dos vértices de diferentes signos, hemos terminado. Sin embargo, la única posibilidad de obtener un ciclo en este gráfico se alternan el blanco y el amarillo de los bordes, de modo que todos los ciclos son, incluso, de hacer nuestra elección posible.

Una pregunta más interesante es lo que ocurre si en lugar de uno, tenemos 5 permutaciones. Sospecho que la respuesta está siendo positiva pero, por supuesto, este enfoque simple tiene que ser modificado para cubrir ese caso.