Problem 478B

Revision en11, by ebanner, 2016-06-12 18:59:07

This problem gave me a great deal of trouble when I first encountered it! I was able to figure out the maximum case (see Tanisha Gupta's answer if you're having trouble) quickly. I also figured out that for the minimum case the solution was to put students in as "uniform" of teams as possible. However, it was figuring out how to put participants in these uniform teams which was the big challenge!

Note: as a matter of notation, the quantity n / m denotes integer truncating division throughout.

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 = (n/m)*m + n%m

Intuitively, this interpretation of n % m can be understood by its computation; by repeatedly summing m (i.e. n/m times) until you get "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 is the number of leftover pieces which don't fit in any of the groups.

Crucially for this problem, it turns out there is actually another interpretation of the quantity n % m, which can be expressed as follows:

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

Equation 2 looks almost identical to Equation 1, 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 (each of size m), whereas here we have m groups (each of size n/m). If this is enough information for you, then go now and solve the problem! If not, then read on for a more detailed explanation.

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) + 2

That is, from 8 pieces we are able to make 2 groups (each 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 illustration 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:

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

All we did was strip off the decimal components (i.e. leftover portions) of each group and moved them off to the right. Notice that the rightmost expression now matches Equation 2 very closely! Concretely, relating this back to Equation 2 we have

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

Even though this equation looks almost identical to Equation 1, we now have exactly m groups (with some leftover), which is exactly what Problem 478B calls for! All that remains now is to distribute the leftover 2 (i.e. 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 participant to each group until we run out of leftover participants. Concretely, in our running example this would be the following:

8 = (2 + 2 + 2) + 2 = (2+1) + (2+1) + 2.

Hence to distribute n participants as evenly as possible into m teams, we will wind up with n % m teams (each of size n/m + 1) and m — (n % m) teams (each of 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)