# Divide N sticks among M boys as homogeneously as possible (ignoring order)

There are $$N$$ sticks. $$N$$ is an integer greater than zero. I want to divide it among $$M$$ boys. $$M$$ is also a positive integer. Partitioning $$N$$ among $$M$$ is easy, but doing it as evenly as possible is difficult for me to think through. Can someone suggest an algorithm? Similar questions exist on this site, but I could not find an answer that solves this problem, though it is possible that I overlooked something.

EDIT:

The sticks are all homogeneous, the same in every respect. What I mean by "as evenly as possible" is that if there are 6 sticks and 3 boys, the division algorithm should output 2-2-2. If there are 5 sticks among 3 boys, it should output 1-2-2. The disparity between the minimum stick holder and maximum stick holder should be minimized. Ordering does not matter (e.g. 1-2-2 is the same as 2-1-2).

• What do you mean by "as equally as possible"? Are the sticks of different lengths/weights? Do you have a link to this problem somewhere? This description seems filled with ambiguity.
– ryan
May 9 '17 at 21:18
• @ryan clarified above. May 9 '17 at 21:46
• You tag "optimization", but what do you want to optimize? Giving everybody nothing it perfectly equal. See here for a more interesting variant.
– Raphael
May 9 '17 at 22:57
• OK, strictly speaking, essentially everything is an algorithm. But you just need to do division, here. May 10 '17 at 19:28
• Dec 13 '19 at 22:36

# Divide perfectly homogeneously, as large as possible
for i = 0 to M
array[i] = N / M    # integer division, resulting in floor

# Divide remainder
for i = 0 to N modulus K
array[i] += 1


Give some of the boys $\lfloor N/M \rfloor$ sticks (i.e., divide and round down), and some of them $\lceil N/M \rceil$ sticks (divide and round up). Once you fix those two numbers, that uniquely determines how many boys get $\lfloor N/M \rfloor$ sticks and how many get $\lceil N/M \rceil$ sticks -- do some simple arithmetic, try a few examples, use the fact that $\lceil N/M \rceil = \lfloor N/M \rfloor + 1$ if $M$ doesn't evenly divide into $N$, and you'll work out the general formula.

Give them $$\lfloor\frac{N}{M}\rfloor$$ sticks and then distribute the rest of sticks ($$N-\lfloor\frac{N}{M}\rfloor$$) among them by giving one stick to each boy until there are no more sticks. By solving it this way, the time complexity will be $$\max(\lfloor\frac{N}{M}\rfloor, N \bmod M)$$ .

• What do you mean by "$[N/M]$"? That's not a notation I've seen before. May 10 '17 at 21:30
• It means the integer part of [N/M] May 14 '17 at 12:17
• Oh, and I have made a mistake about time complexity May 14 '17 at 12:17
• OK. That's usually written $\lfloor N/M\rfloor$ (\lfloor ... \rfloor in LaTeX). May 14 '17 at 13:28
• Yes that is notation for floor. The same upside dow is ceiling. en.wikipedia.org/wiki/Floor_and_ceiling_functions Dec 13 '19 at 22:21