n participants of the competition were split into m teams in some manner so that each team has at least one participant. After the competition each pair of participants from the same team became friends. How will I find the minimum and the maximum number of pairs of friends that could have formed by the end of the competition.
If n=6,m=3 the result is 3,6 and for n=5,m=1, the result 10,10. Can anyone tell me how to solve this problem with better explanation and reasoning.
For $n=6$, $m=3$, we have these possibilities:
The idea is to use the convexity of the function $t \mapsto \binom{t}{2}$. More concretely, for $t \geq 1$ and $s \geq 2$, let us calculate $$ \binom{t+1}{2} + \binom{s-1}{2} - \binom{t}{2} - \binom{s}{2} = t-s+1. $$ This shows that if we move a participant from a team of size $s$ to a team of size $t$, the number of pairs of friends increases if $t \geq s$, remains the same if $t = s-1$, and decreases if $t < s-1$.
Suppose first that we want to obtain the maximal number of pairs of friends. Consider some allocation of participants to teams, and consider the team T with the largest number of participants. The foregoing shows that if we move participants from other teams to T, the number of pairs of friends increases or stays the same. Eventually, we reach a situation in which T contains $n-m+1$ participants, and the rest one participant, for a total of $\binom{n-m+1}{2}$ pairs of friends.
Suppose next that we want to obtain the minimal number of pairs of friends. The foregoing shows that in an optimal solution, there are no two teams sizes $s,t$ satisfying $t < s-1$. Considering the minimal and maximal team sizes reveals that all team sizes are $r,r+1$ for some $r$. The only way to allocate the participants in such an even way is to take $r = \lfloor n/m \rfloor$, have $n \pmod{m}$ teams of size $r+1$, and the rest of size $r$. The total number of pairs of friends is $m \binom{\lfloor n/m \rfloor}{2} + (n\pmod{m})\lfloor n/m \rfloor$.
