2
$\begingroup$

You are given 49 balls of colour red, black and white. It is known that, for any 5 balls of the same colour, there exist at least two among them possessing the same weight. The 49 balls are distributed in two boxes. Prove that there are at least 3 balls which lie in the same box possessing the same colour and having the same weight.

$\endgroup$
  • $\begingroup$ Done, now what? $\endgroup$ – barak manos Mar 28 '15 at 18:34
4
$\begingroup$

This is four successive applications of the pigeonhole principle (PHP).

We can do it various orders, but I will first look at weights within a colour. If any five balls contains two of the same weight, then there are at most four different weights of ball of any colour, by PHP.

Then we look at the number of balls in total. With 49 balls, we must have more than 16 balls of one colour (by PHP).

So, look at the colour (we are guaranteed to have at least one) which has more than 16 balls and at most four different weights of ball. There must, as before by PHP, be at least one weight of the possible four with at least five balls of that weight.

Now, using PHP for the final time, at least one box must have at least three balls of the same colour and weight, and we're done.

$\endgroup$
2
$\begingroup$

It's just one pigeonhole after another...

$49$ balls of three colours

$\implies $ at least $17$ balls of one colour

$\implies $ at least $9$ balls of one colour in one of the boxes.

Any $5$ of those balls have $2$ the same weight

$\implies $ no more than $4$ different weights

$\implies 9$ balls will have at least $3$ the same weight $\square$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.