Back

Solution: 2018 Fall Midterm - 6

Author: Michiel Smid

Question

Let $S$ be a subset of the set $\{1,2,3,\dots,50\}$.
What is the minimum size of this subset $S$, such that there must be at least two elements in $S$ whose sum is equal to 51?
(a)
26
(b)
25
(c)
28
(d)
27

Solution

To find the minimum size of a subset $ S $ of the set $ {1, 2, 3, …, 50 } $

such that there must be at least two elements in $ S $ whose sum is equal to 51, we can use the pigeonhole principle.

Consider the pairs of numbers that sum to 51: [ (1, 50), (2, 49), (3, 48), …, (25, 26) ]

There are 25 such pairs.

If we select more than 25 elements from the set $ {1, 2, 3, …, 50 } $, by the pigeonhole principle, at least one pair will be chosen.

This is because we have only 25 pairs and choosing 26 elements will necessarily include both elements from at least one of these pairs.

Therefore, the minimum size of the subset $ S $ that ensures at least two elements sum to 51 is:

$ boxed{26} $