SCHOOL OF COMPUTER SCIENCE

The Caterer's Problem

You are organizing a conference in social choice theory, 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?

alanATrandomDOTmathDOTcmuDOTedu

  Previous Puzzles and Solutions

Puzzle 38 -- Crush the Rebellion and Solution
Puzzle 37 -- Zeroise Me and Solution
Puzzle 36 -- Nunchuk Supreme and Solution
Puzzle 35 -- Turn on the lights and Solution
Puzzle 34 -- Odd goings on and Solution
Puzzle 33 -- Abduction
and Solution
Puzzle 32 -- The Magic Money Machine
and Solution
Puzzle 31 -- Number Games and Solution
Puzzle 30 -- Darkness
and Solution
Puzzle 29 -- Seating and Solution
Puzzle 28 -- Hiking and Solution
Puzzle 27-- Another Hat Problem and Solution
Puzzle 26-- Coffee
and Solution
Puzzle 25-- Rational Creatures
and Solution
Puzzle 24 -- Fair Shares? and Solution
Puzzle 23 -- Celebrity Problem and Solution
Puzzle 22 -- Can Oleg beat Erdös? and Solution (pdf)
Puzzle 21 -- Searching for the truth
and Solution (pdf)
Puzzle 20 -- Democracy and Solution (pdf)
Puzzle 19 --  Homework Scores and Solution
Puzzle 18 -- Spiders and a Fly and Solution (pdf)
Puzzle 17 -- The Wandering Toad and Solution
Puzzle 16 -- The Hungry Lion and Solution (pdf)
Puzzle 15 -- Hat Problem and Solution (pdf)
Puzzle 14 -- Restrooms and Solution (pdf)
Puzzle 13 --The Voting Problem and solution (pdf)
Puzzle 12 -- Level with me and solution (pdf)
Puzzle 11 -- Quarelling Quartets and solution (pdf)
Puzzle 10 -- Card Tricks and solution (pdf)
Puzzle 9 --Problems with ants and solution (pdf)
Puzzle 8 -- Here comes Santa (pdf) and solution (pdf)
Puzzle 7 --The Gridville Garbash problem and solution (pdf)
Puzzle 6 --Uniform Candy Distribution and solution (pdf)
Puzzle 5 -- Empty the Bucket and Solution
Puzzle 4 ---Vacancy and solution (pdf)
Puzzle 3 ---Take the last chip and solution (pdf)
Puzzle 2 --- Lights of the Round Table and Solution (pdf)
Puzzle 1 --- Managers and Engineers and Solution