Least number of numbers to guarantee two sum to $101$

131 Views Asked by At

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.

1

There are 1 best solutions below

0
On

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