This problem gave me a great deal of trouble when I first encountered it. I figured out quickly enough that the answer to the maximum case was to make the largest team possible while putting as many participants in groups of size 1 to fulfill the requirement of having m groups. I also figured out that the solution for the minimum case was to put students in as "uniform" of groups as possible. It was figuring out how to put participants in these uniform groups which was the challenge!
In hindsight, my main difficulty was that I was lacking the interpretation of n % m necessary for this problem. The interpretation of n % m that has worked for me 99% of the time for me was to view the quantity n % m as the number r such that n = k*m + r, where 0 <= r < m. Intuitively, this can be thought of as repeatedly summing m until it gets within m units of n and then calling the remainder r. Another way to view this procedure is that we are making as many groups of size m out of n as we possibly can. Unfortunately this problem calls for making exactly m groups, which are almost certainly not of size m!
As a review, the quantity n / m expresses the answer to the following two scenarios:
- We have n pieces and want to split them into groups of size m. How many groups are there?
- We have n pieces and want to split them into m groups. How many are in each group?
Since n % m and n / m are intimately related, it turns out that n % m also can be interpreted in both of these ways, also! To illustrate the first interpretation of n % m, consider the example 8 % 3. We can arrive at the answer using the following procedure:
(3 + 3) + 2
Hence 8 % 3 = 2. The procedure we used was to split 8 into groups of size 3 and count the leftover pieces. However, if we want to use the interpretation of making 3 groups, we need to do a little bit more work. In order to illustrate this perspective, consider the analagous illustration of 8 / 3:
2.67 2.67 2.67
That is, if we wish to make 3 groups out of 8 pieces then we need 2.67 pieces in each group. But notice we can manipulate this expression in the following way:
2.67 2.67 2.67 = (2 + 2 + 2) + (.67 + .67 + .67) = (2 + 2 + 2) + 2.
That is, we take the decimal components of each of the groups and move them into their own group. Recall that 8 % 3 = 2. And notice with this alternate procedure we also arrived at a value of 2. This is not a coincidence! The difference here is that instead of making as many groups of size 3 that would get us up to 8 and computing the remainder, we made 3 groups of size 2. This gave us the same answer.
Thinking about it a bit, the operation of "removing the decimal component of a number" is equivalent to integer division (n/m). The sum of decimal components corresponds to n % m. n % m is the stuff left over after adding up these values which are the result of integer division. We are free to distribute the leftover n % m to the groups of 2 however we want. However, for this problem, we are interested in the groups which are as diffuse as possible. It is not hard to see that this is when we "spread out the remainder as much as possible", which corresponds to adding 1 to as many groups of 2 until we have no more remainder.
To sum up, we can compute n % m in the following way:
floor(n/m) floor(n/m) ... floor(n/m) (m times) + n % m
Hence we wind up with n % m teams of size floor(n/m)+1 and m — n%m teams of size n/m.