Pigeonhole Principle: Getting the Largest Sum

Question

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?

Answer 1

I think you are getting mixed up with your question. You are looking for either:

1. The largest possible sum of two numbers chosen from the set of fifteen.
2. The largest sum of two numbers chosen from the set of fifteen, such that this sum appears in every possible set of fifteen.

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