$S$ is a set of $n$ elements with some unknown strict total order. The goal is to discover the greatest $k$ elements, where each step consists of comparing $m\ge 2$ elements at once (so if we compare $a, b,$ and $c$, we might get $b > c > a$). Any strategy for achieving this will have some worst-case number of steps $t$, and our strategy needs to minimize $t$ for the given $n, m,$ and $k$.
This is a generalization of the fastest horses problem, the solution of which can be partially extended to any case with $n=m^2$, and we are left with finding the top $k-1$ elements of $k^2-1$ elements, with the same value for $m$, but we also already know how some of the elements compare, ending up with a structure like:
*>*>*>* *>*>*>* V *>*>* V *>* V *
The problem is proving that a given solution is optimal without an exponential-time brute force search of strategies. Even just proving that starting with the initial strategy I described is always optimal would be very helpful.