Max.

Question

Que $\{n_i\}_{i=1}^k$ ser $k$ natural número así que $\sum_{i=1}^k n_i=n$. Entonces ¿cuál es el máximo de $\sum_\limits{i\neq j} n_in_j$?

Answer 1

Porque $$\begin{align} \sum_{i\ne j}n_in_j &=\left(\sum_{i=1}^kn_i\right)^2-\sum_{i=1}^kn_i^2\\ &=n^2-\sum_{i=1}^kn_i^2 \end{align}$$ Para maximizar $\sum\limits_{i\ne j}n_in_j$ es equivalente a minimizar $\sum\limits_{i=1}^kn_i^2$.

Por Hölder la Desigualdad, $$\begin{align} k\sum_{i=1}^kn_i^2 &=\sum_{i=1}^k1^2\sum_{i=1}^kn_i^2\\ &\ge\left(\sum_{i=1}^kn_i\right)^2\\[9pt] &=n^2 \end{align}$$ y podemos darnos cuenta de este mínimo dejando $n_i=\frac nk$.

Sin embargo, $n_i$ se supone que ser números enteros, por lo que tenemos que hacer un pequeño ajuste. A pesar de que puede no ser capaz de establecer $n_i=\frac nk$ ya que esto podría no ser un número entero, debemos tener la $|n_i-n_j|\le1$. Supongamos que no, y que para algunos $i,j$,$n_i-n_j\gt1$. Entonces $$n_i-n_j-1\gt0$$ y por lo tanto $$\begin{align} (n_i-1)^2+(n_j+1)^2 &=n_i^2+n_j^2-2(n_i-n_j-1)\\ &\lt n_i^2+n_j^2 \end{align}$$ lo que significa que $n_i$ $n_j$ no son parte de un arreglo mínimo. Por lo tanto, debemos tener $|n_i-n_j|\le1$. Esto implica que $n-k\left\lfloor\frac nk\right\rfloor$ de la $n_i$ debe ser igual a $\left\lfloor\frac nk\right\rfloor+1$ y el resto debe ser igual a $\left\lfloor\frac nk\right\rfloor$.

Por lo tanto, con este arreglo mínimo de la suma de los cuadrados, obtenemos $$\begin{align} \sum_{i\ne j}n_in_j &=n^2-\sum_{i=1}^kn_i^2\\ &\le n^2-k\left\lfloor\frac nk\right\rfloor^2-\left(n-k\left\lfloor\frac nk\right\rfloor\right)\left(2\left\lfloor\frac nk\right\rfloor+1\right)\\ \end{align}$$

Answer 2

Puedes rehacer la expresión: $$\sum_{i\neq j} n_i n_j = \sum_i n_i \sum_j n_i - \sum_i n_i^2 = n^2 - \sum_i n_i^2,$$ así que el problema puede ser abordado mediante la minimización de la $\sum_i n_i^2$ bajo la misma restricción.

Evidentemente, para que la solución óptima $$\max_{i,j} |n_i - n_j| \leq 1.$$ De hecho, si no fuera el caso, el valor de la suma podría ser disminuido mediante el movimiento de una unidad de la mayor $n_i$ a la baja. Claramente, una de las soluciones óptimas es tal que el $l$ primeros números son iguales a $a+1$ y el resto es igual a $a$. Entonces $$\sum_i n_i = l (a+1) + (k-l) a = ka + l.$$ Los valores óptimos se $a = n/k$ (división entera), $l = n\%k$ (resto de la división entera). De modo que el valor mínimo de $\sum_i n_i^2$ es igual a $$(n\%k)(n/k+1)^2 + (k-n\%k)(n/k)^2$$ y $$\min \sum_{i\neq j}n_i n_j = n^2 - (n\%k)(n/k+1)^2 - (k-n\%k)(n/k)^2.$$ Tenga en cuenta que cuando se $n\%k = 0$, uno recupera la solución que había encontrado anteriormente en el caso sin restricciones, es decir, $$n^2 - n^2/k$$ (ver la edición de la historia de este post para más detalles)