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
    If $i_4\gt i_3$, it seems to me there are 5 possible positions for $i_9$ and 4 for $i_8$, making 20, one of which (the one where both are between $i_4$ and $i_3$) splits into 2. So I get $21+12=33$.2012-09-07
  • 0
    @Gerry how are there 5 positions for $i_9$ and 4 for $i_8$2012-09-07
  • 0
    Danielle, $i_9$ can be any * in $*i_7*i_1*i_2*i_4*i_3$, and $i_8$ can be any ! in $i_4!i_3!i_5!i_6!$.2012-09-07
  • 1
    @GerryMyerson yes you're correct, I will edit the response. Thanks for pointing that out.2012-09-07