The Caterer's Problem |

You are organizing a conference in social choice theory, with a festive dinner on thefirst 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?

**alan**AT

**random**DOT

**math**DOT

**cmu**DOT

**edu**

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