Learn / Library / Combinatorics

Subset with a fixed sum

CombinatoricsMedium

What is the smallest $n$ such that every set of $n$ different integers chosen from $1$ to $50$ must contain $2$ numbers whose sum is $51$ ?

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

Group the numbers into boxes so that $2$ numbers in one box always add up to the target.

Solution

The numbers split into the $25$ groups $(k, 51 - k)$ for $k = 1, \dots, 25$ , and every group sums to $51$ .
Taking one number from each group gives a set of $25$ numbers with no $2$ summing to $51$ .
Any set of $26$ numbers must take both numbers of some group, by the pigeonhole principle.
Hence the smallest $n$ is $26$ .

Answer: $26$