Partitioning a whole number in a particular way

  • #1
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:

Answers and Replies

  • #2
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
18,110
9,796
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.
 
  • #3
kuruman
Science Advisor
Homework Helper
Insights Author
Gold Member
10,499
3,557
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.
 
  • #4
Dale
Mentor
Insights Author
2020 Award
31,811
8,656
Shouldn’t you just take ##w_i/W## and round to the nearest 1/P
 
  • #5
kuruman
Science Advisor
Homework Helper
Insights Author
Gold Member
10,499
3,557
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.
 
  • #6
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:
  • #7
Dale
Mentor
Insights Author
2020 Award
31,811
8,656
Don’t round up. Round off. It should work unless you get exactly 0.5
 
  • #8
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.
 
  • #9
Dale
Mentor
Insights Author
2020 Award
31,811
8,656
I think that is just because of being exactly 0.5.
 
  • #10
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.
 
  • #11
kuruman
Science Advisor
Homework Helper
Insights Author
Gold Member
10,499
3,557
This sums to 24 but we have 25 pieces.
I faced the same issue when I rounded so I solved the problem by assigning to the last person whatever number of pieces are left unassigned. Simple, no?
 
  • #12
Dale
Mentor
Insights Author
2020 Award
31,811
8,656
Yup, you are right. No 0.5’s so that isn’t the problem
 

Related Threads on Partitioning a whole number in a particular way

Replies
2
Views
3K
  • Last Post
Replies
6
Views
3K
  • Last Post
Replies
8
Views
2K
Replies
14
Views
2K
Replies
5
Views
1K
Replies
1
Views
2K
Replies
0
Views
5K
Replies
1
Views
2K
Top