# Partitioning a whole number in a particular way

Hi,

Let W be the sum of all the people's weights, let P be the total number of pizza slices available.

If:
• I have P slices of pizza (P<=W)
• I have n people I want to split the pizza with
• I want to use people's weight to determine how many slices they get (more weight -> more slices)
• I don't want to split any slices. (I want to leave all slices whole)
• A person cannot eat more slices than the value of their weight. (ai<=wi)

If w1, w2, ... , wn are the weights of the n people, and a1, a2, ... , an are the numbers of slices each of the n people get (where each ai is a whole number >= 0), I want to find the set {a1, ... , an} such that:

ni = 1| ai/P - wi/W |

is minimized.

Is there a formula (some uses of ceiling, floor?) or algorithm to find this set {a1, ... , an} ?

Last edited:

PeroK
Homework Helper
Gold Member
2020 Award
Hi,

If:
• I have P slices of pizza
• I have n people I want to split the pizza with
• I want to use people's weight to determine how many slices they get
• I don't want to split any slices. (I want to leave all slices whole)
How can I decide how many slices to give each person? I know some people may end up with 0 pieces, but that's okay.

You could give all P slices to the heaviest person. Or, to the lightest.

kuruman
Homework Helper
Gold Member
In order to decide how to distribute the slices you need a more quantitative rule (or set of rules) than just "To use people's weight". Use people's weight how? For example, does a heavy, apparently well fed person get more pieces than a skinny, emaciated person or the other way around? What criteria must be met for a person to get at least one piece? And so on.

Of course you can always rely on probability. You can have the people toss coins and get a slice every time they get heads. You assign progressively fewer coin tosses to the people you think should get fewer slices following whatever weight criterion you have.

Dale
Mentor
2020 Award
Shouldn’t you just take ##w_i/W## and round to the nearest 1/P

kuruman
Homework Helper
Gold Member
Shouldn’t you just take ##w_i/W## and round to the nearest 1/P
It depends on one's particular weighting philosophy. I tried some examples using ##(w_i/W)^n##. Positive values of ##n## favor the heavy people while negative values favor the skinny people. One can also try exponentials a la partition function, I guess.

Shouldn’t you just take ##w_i/W## and round to the nearest 1/P

Thanks for the replies.
I don't mind so much favoring someone more than others as long as:

• (ai<=wi) is not violated
• we assign exactly P pieces of pizza. no more, no less
• only whole slices can be assigned (no fractions for ai)

For example, if we have

w1 = 25
w2 = 9
W = 34
P = 17

Then ROUND(P*w1/W) = 13
and ROUND(P*w2/W) = 5

Which means we've just assigned 18 pieces of pizza but we only have 17.

I'm trying to find an algorithm that can ensure we give out exactly the P pieces and we also don't violate (ai<=wi).

Last edited:
Dale
Mentor
2020 Award
Don’t round up. Round off. It should work unless you get exactly 0.5

Don’t round up. Round off. It should work unless you get exactly 0.5

I'm not sure what round off means.

If round off means raise anything with a decimal >= .5 the next whole number and anything with a decimal <.5 to the next whole number down, then the example will still lead to 18 pieces being assigned.

Dale
Mentor
2020 Award
I think that is just because of being exactly 0.5.

I think that is just because of being exactly 0.5.

Another example is:

w1 = 11
w2 = 39
w3 = 3
W = 53
P = 25

ROUND(P*w1/W) = 5
ROUND(P*w2/W) = 18
ROUND(P*w3/W) = 1

This sums to 24 but we have 25 pieces.

kuruman