Caterer's Problem
Source: Puzzle Toad CMU
Problem:
You are organizing a conference, with a festive dinner on the first day. The catering service has 1024 different dinner choices they know how to make, out of which you need to choose 10 to be in the dinner menu (each participant will choose one of these during the dinner). You send an email to the 6875 participants of the conference, with the list of all 1024 choices, asking them to rank the choices in linear order from their favorite to their unfavorite.
You want to find a list L of 10 choices, such that for any dinner choice d not in the list L, if we run a vote of d against L, at least half of people will favor one of the choices in L over d (it may be different dish for different people).
Is it always possible to produce such a list?
Problem:
You are organizing a conference, with a festive dinner on the first day. The catering service has 1024 different dinner choices they know how to make, out of which you need to choose 10 to be in the dinner menu (each participant will choose one of these during the dinner). You send an email to the 6875 participants of the conference, with the list of all 1024 choices, asking them to rank the choices in linear order from their favorite to their unfavorite.
You want to find a list L of 10 choices, such that for any dinner choice d not in the list L, if we run a vote of d against L, at least half of people will favor one of the choices in L over d (it may be different dish for different people).
Is it always possible to produce such a list?
yes its always possible. construct desired list L of dinner choices as per procedure below..
ReplyDeleteLet N be number of dinner choices.
if N=1, then simply we add it to the list; and procedure completes.
otherwise, if N>=2, let A denote arbitrary dinner choice. let F(A) = no. of choices which are ranked below A by majority.
then sigma F(A) = N(N-1)/2., because each pair {A,B} where A and B are different choices, contributes 1 to the sum.
so there exists some choice A such that F(A)>=(N-1)/2 i.e. such that majority prefer choice A over some other (N-1)/2 choices. pl. note that rounding off is to next integer if required thus 6/2=3 and 7/2 rounded to 4.
So, select this one choice A, add it to the list , and along with it remove corresponding (N-1)/2 choices from the consideration zone.
notice that search space is reduced to half. in set of remaining choices, apply this procedure recursively, and so on.
thus in end we will have a list of log N (base 2 ) choices, which will have desired property. where rounding off is to next integer if required i.e. log 2 =1, but log 3 rounded to 2.
It is possible even there are 2^n dinners and you want to find a list of n dinners: we prove this by induction on n. It's pretty obvious when n=1.
ReplyDeleteAssume, then it holds for n-1. When there are 2^n dinners, imagine holding a tournament, where every pair of dinners faces off, and the winner is the one whom more participants prefer. There will be no ties (there are an odd number of participants), so there will be (2^n choose 2) victories total. This means that some dinner must have had 2^(n - 1) - 1 victories, because if everyone had less than this, the total number of victories would be at most 2^n * (2^(n - 1) - 2), which is less than (2^n choose 2). Letting d be a dinner with 2^(n - 1) -1 victories, remove d, along 2^(n - 1) - 1 of the dinners it beats. What remains are 2^(n-1) dinners; by induction, we can find a list of length n - 1 which works for these remaining dinners, then adding d to this list creates a list of length n which works for all 2^n dinners.