# Prove that there must be two distinct integers in $A$ whose sum is $104$.

Let A be any set of $20$ distinct integers chosen from the arithmetic progression ${1,4,7,...,100}$. Prove that there must be two distinct integers in $A$ whose sum is $104$.

Define $A=\{1+3i\}_{i=0}^{33}$. I know that if two distinct integers $a,b \in A$ are such that $104=a+b=(1+3i)+(1+3j)$, then $i+j=34$ with $0<i,j\leq33$ and $i \not= j$.

I think we can play with elements parity or even with the fact that if $i = j$, then $i = 17$ and $(3i + 1) = 52$. However, I am not able to advance further into the question. Are there someone who could help me complete the problem?

• Hint: there are $34$ such numbers. Count the number of pairs $(i,j)$ with $i<j$ and $i+j=104$ you can make out of your set. Then count the number of integers in your set that don't come up in any such pair. – lulu Sep 28 '15 at 23:56
• I know we have 16 such pairs and 20 distinct integers to choose from the sequence. Must I use the pigeonhole principle? – user230283 Sep 29 '15 at 0:08
• Yes. But don't forget that some elements in your progression belong to no such pair. – lulu Sep 29 '15 at 0:14
• I already know that, i.e., when i=0 and i=j. Therefore, I may compute the ceiling of 32/20 = 2. So there must be two elements in which the sum gives 104. Is it right? – user230283 Sep 29 '15 at 0:27
• Not sure I get that last bit. You can choose the two singletons ($1,52$) and you can take one from each of the $16$ pairs. That's $18$ altogether. Whatever you choose next has to complete a pair. So, in fact, unless I have messed up you could replace $20$ in the problem with $19$. – lulu Sep 29 '15 at 0:33

Hint: How many ways can two integers from the progression add up to 104. Lets write them down

$$4+100, 7+97,10+94,\cdots 49+55$$

Those are 16 pairs. We can't take two from any pair, otherwise they would sum to 104.

• I already know, thank you! – user230283 Sep 29 '15 at 0:00

(Historical remark)

This problem is Putnam $78/A1$. You can find a solution here:

Not best possible: we can make do with $19$ elements. Note that the numbers have the form $3n + 1$ for $n = 0, 1, \ldots, 33$. We seek $3n + 1$, $3m + 1$ so that $n + m = 34$. Evidently $n = 0$ and $n = 17$ do not help. The other $32$ numbers form $16$ pairs with the required sum. So if we take $19$ numbers then we are sure to get two from the same pair.