Pigeon Hole. 80 numbered balls

Question

We have $80$ numbered balls(From $1$ to 80).Among which are $45$ blue and $35$ orange. Prove that at least two blue balls differ by $9$. For example $13$ and $22$ or $69$ and $78$.

So they can differ by $1,2,\ldots,79$. Hmm...

Answer 1

If $n$-numbered ball isn't a blue ball, then $n+9$ and $n-9$ are blue balls and there wouldn't be possible for 2 balls to differ by 9.

On opposite if $n$-numbered ball is blue ball, then $n+9$ and $n-9$ are orange balls, because otherwise two of the blue balls will differ by 9.

Now we look at one specific remainder modulo 9. For example let it be $5$.

So to maximize the amount of blue balls we chose $5$ to be a blue ball, then $14$ is orange, $23$ is blue, $32$ is orange, $41$ is blue, $50$ is orange, $59$ is blue, $68$ is orange and $77$ is blue.

So for one remainder at most we can have $5$ blue balls without violating the conditions. So for all 9 remainder we can have 45 blue balls and no two will differ by 9.

But note that when the remainder is $0$ we can have at most $4$ blue balls, so the maximum amount of blue balls and no two will differ by 9 is $44$ and since we have $45$ blue balls by pigeon hole principle there must be at least two blue balls that differ by $9$.

Answer 2

Hint: We can use as pigeonholes the following pairs:

$\{1,10\}$, $\{2,11\}$ and so on up to $\{9,18\}$;

$\{19,28\}$, $\{20,29\}$, and so on up to $\{27,36\}$;

$\{37,46\}$ and so on up to $\{45,54\}$;

$\{55,64\}$ and so on up to $\{63, 72\}$;

$\{64,73\}$ up to $\{71,80\}$.

Note that the first four lists of pigeonholes each have $9$ entries. The last list is special, and has $8$ entries, for a total of $44$.

Answer 3

Take all 45 blue balls. For each ball construct two boxes for its two 9 space neighbors.

Wait!

Every ball has at least one neighbor 9 spaces away and at maximum two 9 spaces away neighbors. But for the balls under 10 and over 71, these lonely balls have only one neighbor 9 spaces away.

So there are at minimum 90 - 18 boxes. You may ask at this point why my young man, so let me explain.

Assuming the worst case in which all the balls under 9 and over 71 are blue (and thus have only one neighbor) there are 90 - 18 possible neighbor spots.

Now every box is allowed to have one spot so this means if you place all 35 orange balls twice, as a ball may at maximum be a 9 space neighbor to two balls, you still have two leftover spots by pigeonhole! Thus these last two spots must be blue.

Answer 4

Let us assume the contrary.

Now, we can easily see that for every blue ball placed at $k$-th, we need to place an orange ball at the $(k+9)$-th place. So, we get $35$ pairs of blue-orange balls without violating our assumed statement and have occupied $70$ positions.

But, from here here on, we are left with $10$ balls which are all blue balls. So, it is obvious by pigeon-hole that we will get atleast $2$ blue balls which differ by $9$ in whatever way we arrange the balls.