6
$\begingroup$

There are $n$ people, and we are allowed to divide them into 2 or more teams (at most $k$, $k \leq n$). It is allowed for a team to consist of only one people. After dividing them, two people will fight if they are from different team. We want to maximize the number of fight, how to best divide those $n$ people?

Example: $n = 6$, $k = 3$ then the optimal way is to divide them into $3$ team each consisting of $2$ people, which will result in $12$ fights.

After some brute force experiment I think the best way is to distribute them into as many team as possible, and each team has member distributed as equally as possible (basically divide them and distribute the result and remainder to all $k$ teams), but I don't know how to prove this.

$\endgroup$
  • 1
    $\begingroup$ You want to maximise the number of edges in a complete $k$-partite graph with $n$ vertices. $\endgroup$ – Arnaud Mortier Feb 1 '18 at 18:50
  • 1
    $\begingroup$ Hint 1: If there are fewer than $k$ teams, subdividing a team will lead to more fights $\endgroup$ – Henry Feb 1 '18 at 18:51
  • 1
    $\begingroup$ Hint 2: If $0 \lt a \le b$ then $(a-1)(b+1) < ab$ $\endgroup$ – Henry Feb 1 '18 at 18:52
1
$\begingroup$

Since a person will fight anyone not in their own team you are looking at half of (with team $r$ having size $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$$

So you want to minimise the sum of the squares of the sizes of the teams.

Now let $a\gt b$ be integers. Then $$(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$ or more you can reduce the sum of the squares.

These observations can be made into a proof.

$\endgroup$
  • $\begingroup$ Thanks, now I see why dividing them as evenly as possible is optimal. But I still don't know how to (formally) proof that dividing them into $k$ teams is optimal instead of some smaller number of team. $\endgroup$ – Allen Walker Feb 1 '18 at 19:25
  • $\begingroup$ @AllenWalker If you have fewer than $k$ teams some of the $a_r$ are equal to zero, so if any of the others are greater than $1$ the same logic applies - the second comment above doesn't depend on the fact that $a$ and $b$ are positive. $\endgroup$ – Mark Bennet Feb 1 '18 at 21:12
1
$\begingroup$

The number of fights with $m$ groups is the number of edges in a complete $m$-partite graph with $n$ vertices. According to this question, this number of edges is $$\dfrac{n^2(m-1)}{2m}$$ This obviously increases with $m$, so you want to use the largest authorised size $m=k$, and the answer is then $$\dfrac{n^2(k-1)}{2k}\text{ fights}$$

$\endgroup$
  • $\begingroup$ well this is certainly a creative way to view the problem $\endgroup$ – Allen Walker Feb 1 '18 at 19:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.