Esquivando permutación sumas

Question

Deje $X =\left (x_1, x_2, \ldots, x_n \right)$ ser una secuencia finita de distintos números enteros positivos, con $n \geq2$, e $S(X) = \left\{ x_1, x_1 + x_2, \ldots, \sum_{i=1}^{j}{x_i}, \ldots, \sum_{i=1}^{n}{x_i} \right\}$ el conjunto de las sumas parciales de la secuencia.

Dado cualquier conjunto $Y = \left\{ y_1, y_2, \ldots, y_{n-1} \right\}$ donde $x_1 < y_k < \sum_{i=1}^{n}{x_i}$, es posible demostrar que siempre existe una permutación de la secuencia de $X$, llama $X^\prime$, de tal manera que $S(X^\prime)\cap Y = \emptyset$?

---

Un geométrica de declaración de la intuición de que el problema podría ser esta: que exista un segmento de línea y un conjunto $X$ $n$ diferentes longitudes, por un total de hasta la longitud del segmento. Dado un conjunto arbitrario $Y$ $n-1$ puntos sobre el segmento, no siempre existe una permutación de $X$, de modo que los puntos que se induce en el segmento no coinciden con ninguna de las $Y$ puntos?

Answer 1

Sí, no siempre existe una permutación.

Vamos a demostrar la generalización donde el $Y$ sólo está obligado a satisfacer $|Y|\leq n-1$ $0<y<\sum_{i=1}^n x_i$ $y\in Y.$ La proposición es verdadera cuando $n=1.$ haremos uso de la inducción, por lo que asume la proposición es verdadera para los más pequeños de $n,$ y tenemos que demostrar por $n.$ Si $Y$ está vacía, no hay nada que demostrar. De lo contrario, hay tres casos. En cada caso se aplica la proposición con $n-1$ $X^@,Y^@$ donde $X^@=X\setminus\{\max X\}$ $Y^@$ depende del caso.

1. $\min Y<\max X$ $\max X\not\in Y$

En este caso vamos a quitar el $y\in Y$ menos de $\max X$ tomando $Y^@=\{y-\max X\mid y\in Y\text{ and }y>\max X\}.$ Anteponer $\max X$ a la permutación de $X^@$ dado por la hipótesis de inducción.

2. $\min Y\leq\max X$ $\max X\in Y$

En este caso vamos a quitar el $\max X$ $Y$ y cambio de los elementos de $Y$ $\max X$ cuando sea posible, mediante la toma de $Y^@=\{y\in Y\mid Y<\max X\}\cup\{y-\max X\mid y\in Y\text{ and }y>\max X\}.$ Anteponer $\max X$ a la permutación de $X^@$ dado por la hipótesis de inducción. El elemento de suma parcial $\max X$ llegará $Y$ $\max X,$ pero podemos solucionar este problema mediante el intercambio de $\max X$ con el siguiente elemento. El primer elemento nuevo no puede ser en $Y^@,$, por lo que no puede ser en $Y.$

3. $\min Y>\max X$

En este caso se suprime $\min Y$ tomando $Y^@=\{y-\max X\mid y\in Y\setminus\{\min Y\}\}.$ Anteponer $\max X$ a la permutación de $X^@$ dado por la hipótesis de inducción. Algunas suma parcial $\max X + x_1 + \dots + x_i$ (adoptando el orden dado por la inducción de la notación) puede golpear $\min Y,$ pero podemos solucionar este problema mediante el intercambio de $\max X$ $x_{i+1}.$