While perusing old unanswered puzzle questions, I came across this one. I found it quite interesting, but a bit vague, so I've decided to recast it.
A party is to be held at a restaurant. The restaurant has the ability to make $D$ different dishes, but the menu for the party will be a fixed menu featuring just $d$ dishes, where $d < D$. To select which dishes should be on the menu, the $n$ guests are asked to rank all D dishes.
For which values of $D$, $d$ and $n$ is it always possible to select $d$ dishes such that for any dish $k$ not on the menu, more than half the guests would prefer one of the dishes in the menu over dish $k$?
Let's look at a concrete example. Suppose the number of possible dishes was $D=10$, the number of selected dishes was $d=3$ and the number of guests was $n=10$. The worst possible ranking I can think of (though I'm not sure it is the worst) is shown below:
The ranks are spread out so no guest ranks any dish the same.
I now selected the $3$ dishes marked in green so that the ranks of $1,2, 3$ were distributed among the guests as much as possible. Thus, only guest $10$ does not have one of the selected dishes in his top $3$.
If you now go through each of the unselected dishes, you will see that in every case a majority of the guests will have a higher ranked dish among the $3$ selected dishes.
So (assuming my worst case actually is the worst case!) with these values of $D$, $d$ and $n$, it is always possible to select such a menu.
Any input as to whether a worse case ranking is possible, would also be appreciated.
EDIT - Partial results
After fiddling with this question, I realize I should probably have asked "Given $n$ and $D$, what is the minimum required $d$ to fulfill the constraint?". Afterall, if a certain value of $d$ works, then so will any larger value of $d$.
My biggest problem, oddly, is how to know the worst possible ranking. To test conjectures, I need to test them against the worst case. But I'm not completely sure what that is, for a given $n$ and $D$.
Anyway, an initial result is that a menu is always possible if $d > \frac{n}{2}$.
A second tentative result is that if $n = D$ then $d = 2$. E.g., if I select dish $1$ and $6$ in my example above, the constraint is fulfilled.
But this implies that if a $1000$ people ranked a $1000$ dishes, it would still be possible to select $2$ dishes that fulfilled the constraint. This doesn't seem right. But if I use the "worst case" scenario which I used in my example above, this is the result I get.
I'd appreciate if someone could post a counter-example. I suspect the problem is that my "worst case" is not the actual worst case.
EDIT2 - Outragous!
Further fiddling and computer simulation suggests the outragous claim that if $n \ge D$ then still $d = 2$. This implies that if a $1,000$ dishes were ranked by a $1,000,000$ guests, we could always find just $2$ dishes which fulfilled the constraint! I must be doing something wrong.
As usual, counter-examples would be greatly appreciated.
EDIT3
So I've now done $10,000$ simulations with $30$ dishes and $60$ guests, where the guests ranked the dishes randomly, and in every case a menu of just $2$ dishes was sufficient. My confidence that $2$ dishes will always be sufficient for $n \ge D$ grows. :-)
But a proof or counter-example would be nice.
Now to look at $n < D$.