1
$\begingroup$

Suppose I have 9 integers such that

$i_1>i_2>i_3$

$i_4>i_5>i_6$

$i_7>i_1$

$i_2>i_4>i_8$

and $i_9>i_3>i_5$.

From this we then know that as $i_3>i_5$ and $i_4>i_5$ then $i_7>i_1>i_2>i_5$, and we can make similar deductions.

Given this information how many possible rankings of largest to smallest are there for $i_1$ through $i_9$?

1 Answers 1

2

Construct the largest possible chain of inequalities:

$i_7>i_1>i_2>i_3>i_5>i_6 $

Condition $i_2>i_4>i_5$ gives 2 possible positions for $i_4$:

  • $i_4>i_3$ leaves 5 possible positions for $i_9$, and 4 possible positions for $i_8$. Additionally the case $i_4>i_8>i_9>i_3$ should be considered.

Therefore we have $5\cdot 4+1=21$ possible arrangements if $i_4>i_3$.

  • $i_3>i_4$ leaves 4 possible positions for $i_9$, and 3 possible arrangements for $i_8$. Since $i_9>i_3>i_4>i_8$ we need look no further.

Therefore we have $4\cdot 3=12$ possible arrangement if $i_3>i_4$.

Total is $21+12=33$ possible arrangements.

  • 1
    @GerryMyerson yes you're correct, I will edit the response. Thanks for pointing that out.2012-09-07