Números de corte en piezas

Question

Deje $x_1,x_2,\dots,x_n$ ser enteros positivos escrito en una línea, y $k\leq n$ un entero positivo. Podemos cortar siempre los números en $k$ partes de acuerdo a la línea de pedido para satisfacer la siguiente propiedad: Para cada parte, hay un número en uno de los dos extremos de la parte de que si nos la quita, entonces la suma de los números en la parte no es mayor que la suma de los números en cualquier otra parte?

Una idea es utilizar la inducción en $k$. Para $k=1$ no necesitamos cortar cualquier cosa, por lo que la instrucción es trivialmente cierto. Para mayor $k$, si podemos demostrar que siempre hay un "punto de corte" para cortar la primera parte y, a continuación, utilizar la hipótesis de inducción a cortar el resto de los números en $k-1$ partes, nos llevaría a cabo. Sin embargo, no es obvio cómo encontrar este punto de corte o si siempre existe.

Otra cosa a tener en cuenta es que si $k=n$, que acaba de cortar los números en $n$ partes con un número cada uno, y de nuevo este trivialmente obras.

Answer 1

Como nota, sólo necesitamos considerar $k<n.$

Hay un valor de $V>0$ satisfactorio $$V=\frac1k\sum_{i=1}^n\min(x_i, V).$$

Para ver esto, observe que ambos lados son continuas en a $V,$ $V=\min_ix_i$ el lado derecho es más grande, mientras que para $V>\tfrac 1k\sum_{i=1}^nx_i$ el lado izquierdo es más grande. Definir

$$x_i'=\min(x_i,V)$$ $$S_j=\sum_{i=1}^jx_i'\qquad(0\leq j\leq n)$$

con $S_0=0.$ $S_n=kV.$

Para cada una de las $0\leq j\leq k$ deje $i_j$ ser el más grande de $0\leq i\leq n$ $S_{i_j}\leq jV.$

Si $x'_1+\dots+x'_{i_1}<x'_{2+i_{k-1}}+\dots+x'_n,$, a continuación, invierta la secuencia y volver a calcular todas las $S_j$ $i_j$'s. Esto básicamente permutas $x'_1+\dots+x'_{i_1}$ $x'_{2+i_{k-1}}+\dots+x'_n,$ porque $i_{k-1}$ fue elegido como el más pequeño índice con $x'_{2+i_{k-1}}+\dots+x'_n<jV.$ La desigualdad estricta se intercambia con un no-estricta, pero que trabaja en nuestro favor. El resultado es que el $S_1\geq S_n-S_{1+i_{k-1}}.$

Tomar la $j$'th parte de consistir $x_{1+i_{j-1}}$ $x_{i_j}.$ Tenemos $S_n=kV,$$i_k=n,$, por lo que cada número se obtiene una parte. Desde $S_{j+1}\leq S_j + V,$ la secuencia de $i_j$ es estrictamente creciente, lo que significa que cada parte no está vacía. Para el $j$'th parte, si se elimina el primer elemento, la suma restante de $x'_i$'s está limitada por $S_{i_j}-S_{1+i_j}<jV-(j-1)V=V;$ esta obligado es válido para la imprimado $x_i$ desde una secuencia cuya suma es menor que $V$ no puede contener ningún elemento mayor que $V.$ Desde $S_{i_{k-1}}\leq (k-1)V,$ la parte final tiene suma, al menos, $V.$ Y la reversión de paso en el párrafo anterior se asegura de que $S_1\geq S_n-S_{1+i_{k-1}},$, de modo de quitar el primer elemento de la última parte deja su suma en la mayoría de los tan grande como la suma de la primera parte (y de nuevo, la cantidad de $S_n-S_{1+i_{k-1}}$ es un límite para la imprimado $x_i$, ya que está a menos de $V.$)