Cómo resolver esto (tal vez) la combinatoria problema?

Question

Hay $n$ de la gente, y nos han permitido dividir en 2 o más equipos (en la mayoría de los $k$, $k \leq n$). Es permitido para un equipo que constan de una sola de las personas. Después de la división, dos personas se lucha si son de distintas equipo. Lo que queremos es maximizar el número de luchar, cómo la mejor manera de dividir los $n$ de la gente?

Ejemplo: $n = 6$, $k = 3$ a continuación, la forma óptima es la de dividir en $3$ equipo de cada uno de ellos compuesto de $2$ de la gente, lo que resultará en $12$ peleas.

Después de algo de fuerza bruta experimento, creo que la mejor manera es la distribución de ellos en el equipo que muchos como sea posible, y cada equipo tiene miembros distribuidos de la forma más equitativa posible (básicamente, dividir y distribuir el resultado y el resto de todas las $k$ de los equipos), pero no sé cómo probar esto.

Answer 1

El número de peleas con $m$ grupos es el número de aristas en una completa $m$-partita gráfico con $n$ vértices. De acuerdo a esta pregunta, este número de aristas es $$\dfrac{n^2(m-1)}{2m}$$ Esto, obviamente, aumenta con la $m$, por lo que usted desea utilizar el mayor autorizados tamaño de $m=k$, y la respuesta es, a continuación, $$\dfrac{n^2(k-1)}{2k}\text{ fights}$$

Answer 2

Ya que una persona va a luchar contra alguien que no esté en su propio equipo que usted está buscando en la mitad (con el equipo de $r$ tiene un tamaño $a_r$)$$\sum_{r=1}^k a_r(n-a_r)=n\sum a_r-\sum a_r^2=n^2-\sum a_r^2$$

Así que usted quiere minimizar la suma de los cuadrados de las dimensiones de los equipos.

Ahora vamos a $a\gt b$ ser números enteros. Entonces $$(a-1)^2+(b+1)^2=a^2+b^2+2(b+1-a)\le a^2+b^2$$ with equality only if $a=b+1$. So whenever you have teams which differ by $2$ o más, usted puede reducir la suma de los cuadrados.

Estas observaciones pueden ser hechas en una prueba.