0
$\begingroup$

I have a pigeon hole principle question that I'm stuck on and would appreciate some help.

10 balls are labelled between 1 and 10. The balls are partitioned amongst 5 people. Prove that no matter how the balls are partitioned there will be at least one person that holds balls with values that add up to 11 or more. Use the pigeon hole principle.

I'm having trouble determining what the pigeon holes and pigeons would represent in this case.

$\endgroup$
  • $\begingroup$ HINT Just compute the sum of all the balls $\endgroup$ – Bram28 Dec 16 '17 at 21:56
2
$\begingroup$

Just compute the sum of all the balls, which is $55$: so you have $55$ 'pigeons', and if for each of the $5$ persons the value of the balls they get can add up to at most $10$ points, then there would only be $50$ 'pigeonholes'.

So the pigeons and pigeonholes are the values or points on the balls, rather than the balls or the persons themselves.

$\endgroup$
0
$\begingroup$

The sum of the balls are the pigeons and the people are the pigeon holes.

You now have $55$ pigeons for $5$ pigeon holes, which means that at least one hole will have more than $10$ pigeons.

$\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.