We are given an ordered $n$-tuple of positive real numbers $R=(r_1,..r_n)$. A $k$-inequality is an inequality of the form
$x_1<x_2<...<x_k$
where $x_1,..,x_k$ are in $R$. For example, for $n=7$, we might have the $3$-inequality $r_5<r_2<r_1$. We would like to order by magnitude all the elements in $R$ given some number of $k$-inequalities.
(1) Find the minimum number of $k$-inequalities such that the ordering is determined.
(2) Find the maximum number of $k$-inequalities one can give such that the ordering is not determined.
I made up this problem yesterday, but I'm guessing that this is a well known thing in computer science/information theory/algorithms.
Assume $r_1<r_2<\ldots<r_{n-1}<r_n$.
For $k=2$, the answers are (1) $n-1$ and (2) $\binom{n}2-1$.
In the first case, we can write $r_1<r_2,\ r_2<r_3,\ \ldots,\ r_{n-1}<r_n$.
In the second case, we can write all possible inequalities with $r_1$ as the lesser: $r_1<r_2,\ r_1<r_3,\ \ldots,\ r_1<r_n$ and then all the inequalities with $r_2$ as the lesser, etc., until we reach $r_{n-1}<r_n$, without which the order is not totally decided.
For $k=3$, in the first case we can write $r_1<r_2<r_3$, then $r_3<r_4<r_5$, etc. and establish the order in just $\lceil \tfrac12(n-1)\rceil$ statements.
In the second case, I suspect the answer is $\tbinom{n}3-(n-2)$. Write down all the 3-inequalities except for those which end $\ldots<r_{n-1}<r_n$.
For general $k$, the analogous answers would be (1) $\lceil \tfrac{n-1}{k-1}\rceil$ and (2) $\binom{n}k-\binom{n-2}{k-2}$.