Problem 478B

Revision en7, by ebanner, 2016-06-12 17:37:47

This problem gave me a great deal of trouble when I first encountered it! I was able to figure out quickly enough that the answer to the maximum case is to make the largest team possible while putting as many participants in groups of size 1 in order 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, the reason this gave me so much trouble was because I was lacking the interpretation of n % m necessary for this problem. My tried and true understand of the quantity n % m has always been the following:

n % m = m — (n/m)*m

Intuitively, this interpretation of n % m can be computed by repeatedly summing m (i.e. n/m times) until it gets "close" to n and then calling the remainder n % m. Another way to view this procedure is that we start off with n pieces and split them into groups of size m (there are n/m of these groups) and n % m represents the leftover pieces which don't fit in any of the groups.

This interpretation of n % m has always been sufficient for me. However, there is actually another interpretation of the quantity n % m! It can be expressed as follows:

n % m = m — m*(n/m)

This equation looks almost identical to the one above, but it's computed in a very different way! n % m still represents the number of leftover pieces after forming groups, but the nature of the groups differ here. In Equation 1 we had (n/m) groups of size m, whereas here we have m groups, each of size (n/m). If this clicks for you (it did not for me), then feel free to skip the following discussion. If not, then read on for an example!

In order to explain Equation 2, I am first going to illustrate Equation 1 with an example. To this end, consider the quantity 8 % 3. We can write it down as follows:

8 % 3 = (3 + 3) + 2.

That is, from 8 pieces, we are able to make 2 groups of size 3, but we cannot make a third, so the number of leftover pieces (i.e. 8 % 3) is 2.

With this understanding, consider the following interpretation of 8 / 3:

8 = 2.67 + 2.67 + 2.67

Here, we start with 8 pieces and split them into 3 groups. The quantity 8 / 3 represents the number of pieces in each group (which is 2.67). Now we can manipulate the expression in Equation 3 in the following way:

2.67 2.67 2.67 = (2.0 + 2.0 + 2.0) + (.67 + .67 + .67) = (2 + 2 + 2) + 2 = 3*2 + 2.

That is, we take strip off the decimal components of each of the group sizes and move them to the right. Notice that this now matches equation (2) exactly. That is, we have:

8 % 3 = 3*(8/3) + 2.

Even though this equation looks almost identical to equation (1), we computed it in a much different way!

Relating this back to the original problem, all that remains is to distribute the leftover n % m participants as evenly as possible into the m groups we've computed. It's not hard to see the way to do this is to add one student to each group until we run out of leftover participants. Thus we wind up with m total teams, n % m of which have size floor(n/m)+1 and m — n % m of which have size n / m.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en27 English ebanner 2016-08-14 17:35:13 39 Tiny change: 'rite, but actually we can no' - (published)
en26 English ebanner 2016-08-14 17:27:58 2 Tiny change: 'to create m teams as ' -> 'to create `m` teams as '
en25 English ebanner 2016-08-14 17:27:31 130 Tiny change: ' quantity n / m denotes i' - (saved to drafts)
en24 English ebanner 2016-06-13 04:12:32 3 Tiny change: 'cipant to different teams. As a res' -> 'cipant to a different team. As a res'
en23 English ebanner 2016-06-13 04:11:59 3 Tiny change: 'rticipants)! All that ' -> 'rticipants!). All that '
en22 English ebanner 2016-06-13 04:11:12 74 Tiny change: 'rite, but we can no' -
en21 English ebanner 2016-06-12 20:45:49 12 Tiny change: ' However, this problem requires ' -> ' However, Problem 478B requires '
en20 English ebanner 2016-06-12 20:44:53 2 Tiny change: '%m.\n\nIn English, Eq' -> '%m.\n\nIn english, Eq'
en19 English ebanner 2016-06-12 20:41:36 42 Tiny change: 'nd up with the following equation:\n\nn = (n' - (published)
en18 English ebanner 2016-06-12 20:38:51 140 Tiny change: ' English, this can be re' - (saved to drafts)
en17 English ebanner 2016-06-12 20:28:32 11 Tiny change: 'th how to quantify that. Thi' -> 'th how to compute that. Thi'
en16 English ebanner 2016-06-12 20:26:07 75
en15 English ebanner 2016-06-12 20:23:25 28
en14 English ebanner 2016-06-12 20:21:42 133 Tiny change: 'nts.
en13 English ebanner 2016-06-12 20:11:08 301 Tiny change: 'buting n people into m te' - (published)
en12 English ebanner 2016-06-12 19:58:36 2947 Tiny change: 'ially. My understan' - (saved to drafts)
en11 English ebanner 2016-06-12 18:59:07 87
en10 English ebanner 2016-06-12 18:54:04 57 Tiny change: 'ave:\n\n8 % 3 = 3*2 + 2' - (published)
en9 English ebanner 2016-06-12 18:45:19 531 Tiny change: 'possible. It was figu' -
en8 English ebanner 2016-06-12 17:50:02 776 Tiny change: '2 + 2.\n\nHere we stripped off the d' -
en7 English ebanner 2016-06-12 17:37:47 898 Tiny change: '; (n/m)*m _(1)_\n\n' -
en6 English ebanner 2016-06-12 17:12:48 2108 (saved to drafts)
en5 English ebanner 2016-06-12 00:02:01 693 Tiny change: 'ins is to the remaining n % m par' - (published)
en4 English ebanner 2016-06-11 23:50:24 1111 Tiny change: ' related, n % m als' -
en3 English ebanner 2016-06-11 23:35:23 523 Tiny change: '7 + .67)\n ' -
en2 English ebanner 2016-06-11 22:47:14 871
en1 English ebanner 2016-06-11 22:00:44 1291 Initial draft (saved to drafts)