Chef's Delight

An interesting puzzle straight from CMU

You are chef for a day. There are 1024 different dishes you can make, but you need to pick 10 for the dinner menu. You've emailed the 3775 attendees a list of all the dishes and asked them to rank all the dishes in order of their preference (ranks go all the way from 1,2,3 … to …1024)

Now, you're trying to make a list of 10 dishes, let's call it List L. This list should have a special quality: if there's a dish 'd' that's not on List L, and you compare 'd' to the dishes on List L in a vote, then at least half of the people should like one of the dishes on List L more than 'd'. Different people might prefer different dishes.

The big question is: Can you always make a list like that?

---

Try to solve this problem yourself before moving on to the solution below

.
.
.

.

.

---

Solution

Short answer : It is always possible

Long answer:

It is possible even there are 2^n dishes and you want to find a list of n dishes: we prove this by induction on n. It's pretty obvious when n=1.

Assume, then it holds for n-1 . When there are 2^n dishes, imagine holding a tournament, where every pair of dishes faces off, and the winner is the one whom more participants prefer. There will be no ties as there are an odd number of participants, so there will be (2^n choose 2) victories total.

This means that some dish must have had atleast 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).

Now simply, select a dish with 2^(n - 1) -1 victories, remove that dish, 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 dishes, then adding this dish described by this method to our menu recursively creates a list of length n which works for all 2^n dishes.

.

.

😃 Over to you: Were you able to solve this?

---

👉 If you liked this post, don’t forget to leave a like ❤️. It helps more people discover this newsletter on Substack and tells us that you appreciate solving these weekly questions. The button is located towards the bottom of this email.

👉 If you love reading this newsletter, feel free to share it with friends!