Originally Posted by

**usagi_killer** Yeah I got that counter example too, the solutions do it like this: (It makes sense so I don't know where the fallacy is)

Let $\displaystyle a_i$ denote the position of the $\displaystyle i$th available item. We must show that $\displaystyle a_i-a_j = 9$ for some i and j. Consider the numbers:

$\displaystyle a_1, a_2, \cdots, a_{45}$ ...[1]

and

$\displaystyle a_1+9, a_2+9, \cdots. a_{45}+9$ ...[2]

The 90 numbers from [1] and [2] have possible values from 1-89. So by the form of the pigeonhole theorem I stated in the OP, two numbers must coincide. We cannot have two of [1] or two of [2] identical, thus some number in [1] is equal to some number in [2]. Therefore $\displaystyle a_i = a_j+9 \implies a_i-a_j = 9$ for some i and j.

Now I understand their working but obviously there exists a counterexample, so where is the fallacy in their working?

Many thanks again!