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

来源: 2007-09-24 16:26:24 [博客] [旧帖] [给我悄悄话] 本文已被阅读:

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.