SPOILER: My proof on why solution idea works

Posted by

John 14 Jan 2022 16:36

So we must try to make teams have equal size. Why?

Consider two teams with x and y members respectively, and consider x > y. Sending a member from first team to second team will only affect matches between these two teams. At first we have x*y different matches between the teams. If we send a player to the second team, there are now x-1 and y+1 members in each team. The matches are now

(x-1)*(y+1) = x*y + (x-y) - 1

As we said x > y, x-y > 0, so x-y-1 >= 0 and our change can't reduce the total number of matches, so it is an optimal change.

This also shows that nothing changes when x = y+1, so if we can't make all teams equal size, just add each of the ones remaining into a different team, making a difference of at most 1 in the sizes of teams.

Now it's your job to compute the number of matches, I won't show that, but it can be done with a one line formula. Good luck :)