I'm struggling currently with one of my problems in my homework. The professor gave two hints to the following problem.
Problem: Find the least amount of different numbers to pick from positive integers that are at most $100$ to guarantee two pairs of numbers that add up to $101$.
Hints:
- Show that $n$ is sufficient to guarantee
- Show that $n-1$ is not sufficient
Although I understand the basic logic of the pigeon hole principle, I would greatly appreciate it if in the answer, the definition of the pigeon hole is expanded upon.
Number $100$ cards, and place them into two columns of $50$ rows each, such that each row sums to $101$.
Now it is obvious that you can only take at most one card from each row and not take two that sum to $101$. This gives you $50$ cards. After that, every card gives a pair, so $52$ cards guarantees two pairs.
$51$ cards isn't sufficient, for example you could pick $1-51$.