Great! There might be a problem, but can be fixed.

本帖于 2007-09-25 09:39:38 时间, 由普通用户 康MM 编辑
回答: 回复:可接受的分配方案乱弹2007-09-23 20:28:05

Namely, it is possible that every slice is wanted by many people.

We can use the marriage theorem to fix this. If for any m slices, there are no less than m people such that each of them like at least one of these m slices, then the marriage condition is satisfied, and there is a perfect matching: everyone can get one slice he likes.

Otherwise, let m be the smallest number such that there are m slices and less than m people like at least one of them. Now we can do a match and let each of these people get one slice and go: others won't complain since they do not like any of these m slices, which means for them, each of these m pieces is less than 1/N and they think they are left enough.

Then this procedure continues until everyone is happy.

请您先登陆,再发跟帖!