# Pigeonhole Principle: Getting the Largest Sum

Problem:

Choose 15 different numbers in sequence 1, 4, 7, 10, 13, ..., 64, 67, 70 to form a group. What is the maximum sum of any 2 numbers selected from the set of the 15 different numbers?

Solution:

There are 24 numbers in the sequence. Using pigeonhole principle, since 15 numbers will be picked from the set, there are at least one pair of numbers whose sum is 83. So the largest sum is 83.

However, I don't get the idea of using the pigeonhole principle if we can choose 67 and 70. So, the sum is 137?

• It says that there's a sum that'll appear in all sets, but asks you to find the largest sum? – MalayTheDynamo Jul 24 '18 at 15:33

In the first case the answer is $67+70 = 137$.
In the second case the answer is the sum of the two largest elements in the smallest set, namely $40 + 43 = 83$. As the elements are in a arithmetic progression, using the pigeonhole principle you can show why there must be at least two elements in any set of fifteen which also add to $83$.