# Minimize number of comparisons to discover a strict total order

$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.

• Is this simply the generalized $k$ fastest horses problem? – ryan Nov 12 '17 at 1:04
• Also, to clarify, you're not looking for minimum number of comparisons, you're looking for minimum number of calls to this $m$-ary function that return a total order on the $m$ elements, correct? You may want to rephrase your title. – ryan Nov 12 '17 at 1:53
• @ryan Yep, that was the inspiration for my exploration of the generalization. And it is the number of calls to the $m$-ary function that counts. – Fricative Melon Nov 12 '17 at 1:56
• The exact optimum probably isn't known in general, though there are some conjectures stating that the optimum isn't far away from the trivial lower bound. See for example en.wikipedia.org/wiki/1/3%E2%80%932/3_conjecture. – Yuval Filmus Nov 12 '17 at 11:42