Problem
Imagine you have some set of $N$ elements (say, movies), and group of people who collectively have a complete ranking of these movies. You can poll them with a subset of the movies to see how they rank that subset, but you can only list $k$ options per poll. How many polls $p(N,k)$ do you need to run to guarantee a full ranking of the movies according to the group's preferences?My Attempts
I've tried to think of simplifications and ways to phrase the problem more mathematically/abstractly, just to get the juices flowing and help find an angle of attack. I first considered the overly simplified case where we don't have the transitive property, so $a_1 < a_2$ and $a_2 < a_3$ does not give us $a_1 < a_3$. Thus for every $1\le i,j \le N$, we must have $a_i$ and $a_j$ in the same poll somewhere. This should be a much easier problem to solve, and it should at the very least provide an upper bound on $p$, since adding transitivity should only decrease the amount of polls needed. Phrased the entire question more mathematically:
- Given a set $A=\{a_1,...,a_N\}$ how many subsets of size $k$ are required such that for any $1\le i,j\le N$, there exists a subset $B\subset A$ such that $a_i,a_j\in B$?
This problem alone seems to be quite difficult. There are some trivial cases like $k=2$ for which the answer is clear, but a more general solution still eludes me. I did find this MIT-Harvard math competition which seems to develop a framework very well suited for addressing this problem, but after working through it, I am still at a loss for an angle of attack on this smaller problem. It does note at the end the connection between the framework that was built up and graph theory/hypergraph theory, but I'm bad enough as it is with regular graph theory, I can't imagine finding much use personally from hypergraph theory (which my intuition says will be the analogous case for any $k>2$).
In terms of possible approaches on the original problem, I briefly considered thinking of algorithms using posets or orderings just to provide some non-trivial bounds, but got pretty much nowhere on those avenues.
In This Thread
Given my struggle to solve this problem, unless I've missed some major oversight, I'm not expecting a whole solution. Rather, I've seen plenty of threads here before which are less of a Q&A format, and are more of a collaborative approach to a fun problem which nobody has a concise solution to. My hope is that this can be one of those threads!
Note: I'm aware the title and tags may not be the best; if you have any ideas on improving them, let me know and I can edit them.