Combinatorics pigeonhole principle question.

294 Views Asked by At

There are $n$ people at a meeting, each of whom chooses $3$ distinct numbers between $1$ and $11.$

$\quad({\sf a})$ What is the smallest value of $n$ which guarantees that at least two people choose numbers which sum to the same total?

$\quad({\sf b})$ What is the smallest value of $n$ which guarantees that there is a number which is chosen by at least two people?

$\quad({\sf c})$ What is the smallest value of $n$ which guarantees that at least two people choose the same set of three numbers?

I get that I need to use pigeonhole principle, but I don't get where and how?

1

There are 1 best solutions below

23
On

A start: The smallest possible sum of three is $6$, the biggest is $30$, and all sums in between are achievable. That gives $25$ possible sums. Call these the pigeonholes. How many pigeons do we need to make sure there are at least two in some pigeonhole?