Deje $x_1,x_2,\dots,x_{100} $ ser una permutación de $1,2,\dots,100.$ ¿cuántos valores diferentes que hace la suma de $ x_1+2x_2+\cdots+100x_{100}$?
Respuesta
¿Demasiados anuncios?
Deje $x_1,x_2,\dots,x_n$ ser un permutaciones de $1,2,\dots,n.$ $(n\ge 4)$.
Luego hay
$$ \dfrac{n(n-1)(n+1)}{6}+1 $$ los diferentes valores de las sumas $ x_1+2x_2+\cdots+nx_n$.
El valor más pequeño es $$v_n = 1\cdot n + 2(n-1)+3(n-2)+\cdots+n\cdot 1 = \sum_{j=1}^{n}j(n+1-j)=\dfrac{n(n+1)(n+2)}{6},$$ valor más grande es $$ V_n = 1\cdot 1+2\cdot 2+\cdots+n\cdot n = \sum_{j=1}^nj^2= \dfrac{n(n+1)(2n+1)}{6}. $$
Vamos a demostrar que no hay "huecos" entre el$v_n$$V_n$.
Vamos a usar las matemáticas. de inducción.
0) no Hay "lagunas" de $n=4$.
Realmente,
$(4,3,2,1)\rightarrow 20$;
$(4,2,3,1)\rightarrow 21$;
$(3,4,1,2)\rightarrow 22$;
$(3,2,4,1)\rightarrow 23$;
$(4,1,2,3)\rightarrow 24$;
$(3,1,4,2)\rightarrow 25$; ... (otro de los casos - de forma simétrica).
1) Supongamos que no hay "lagunas" para algunos $n=n_0$.
2) probar Ahora que no hay "lagunas" de $n=n_0+1$:
2.a) todas las sumas de vectores $(n_0+1, x_1,x_2,\ldots,x_{n_0})$ tiene forma $$ 1(n_0+1)+2x_1+3x_2+\cdots+(n_0+1)x_{n_0} \\= n_0+1+(x_1+x_2+\cdots+x_{n_0})+(x_1+2x_2+\cdots+n_0 x_{n_0}) $$ y rellenar los valores de $$ n_0+1+\dfrac{n_0(n_0+1)}{2}+\dfrac{n_0(n_0+1)(n_0+2)}{6} = \dfrac{(n_0+1)(n_0+2)(n_0+3)}{6} = v_{n_0+1}$$ a $$ n_0+1+\dfrac{n_0(n_0+1)}{2}+\dfrac{n_0(n_0+1)(2n_0+1)}{6} = \dfrac{2n_0^2+4n_0+6}{6} $$ sin "huecos";
2.b) todas las sumas de vectores $(x_1,x_2,\ldots,x_{n_0},n_0+1)$ tiene forma $$ x_1+2x_2+\cdots+n_0x_{n_0}+(n_0+1)(n_0+1) \\= (x_1+2x_2+\cdots+n_0 x_{n_0}) + (n_0+1)^2 $$ y rellenar los valores de $$ \dfrac{n_0(n_0+1)(n_0+2)}{6} + (n_0+1)^2 = \dfrac{n_0^2+8n_0+6}{6} $$ a $$ V_{n_0}+(n_0+1)^2 = \dfrac{(n_0+1)(n_0+2)(2n_0+3)}{6}=V_{n_0+1}. $$ sin "huecos".
2.c) queda por mostrar que el límite superior de 2.a) no es menor que el límite inferior de 2.b). Es así que, desde $$ n_0\ge 4\\ \Downarrow \\ n_0^2 \ge 4n_0 \\ \Downarrow \\ 2n_0^2 \ge n_0^2+4n_0 \\ \Downarrow \\ 2n_0^2 +4n_0+6\ge n_0^2+8n_0+6. $$
Y su aplicación a la $n=100$.
