Choosing pairs of numbers with distinct bounded sum

Question

Stumbled across this problem in the list of examples for high school math exam, paraphrasing a little:

What is the maximum number of pairs with integers from 1 to 22 you can choose,
with each pair having a distinct sum that would not exceed 27?

After playing with numbers for a bit, my intuition tells me that it's definitely not 11, but what is the correct answer (seems like 9, because I can't make 10), and more importantly, how to prove it, I have no idea. Does anyone have some idea of the approach to this problem?

score 1 · Accepted Answer · answered Jun 02 '16 at 10:08

1

The 10 pairs: (17,10),(14,12),(21,4),(13,11),(20,3),(16,6),(19,2),(18,1),(9,8),(7,5) are disjoint and have distinct sums in the range 12-22.

If 11 pairs were possible, then their total sum would be 1+2+...+22=253. But the greatest possible sum for 11 pairs with distinct sums is 17+18+...+27=242. So 11 pairs are not possible.

answered Jun 02 '16 at 10:08

almagest

18,380

op said pairs have distinct sums, he didnt say numbers are distinct . – Abr001am Jun 02 '16 at 10:17
Guess I didn't try hard enough to make 10 pairs, is it just from trial and error? – swish Jun 02 '16 at 10:18
@Agawa001 The question would be trivial if you took that interpretation. It also does not square well with his comments in the last paragraph. – almagest Jun 02 '16 at 10:19
@swish Yes, more or less. – almagest Jun 02 '16 at 10:20

Choosing pairs of numbers with distinct bounded sum

1 Answers1