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?

  • $\begingroup$ 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. $\endgroup$ – lulu Sep 28 '15 at 23:56
  • $\begingroup$ I know we have 16 such pairs and 20 distinct integers to choose from the sequence. Must I use the pigeonhole principle? $\endgroup$ – user230283 Sep 29 '15 at 0:08
  • $\begingroup$ Yes. But don't forget that some elements in your progression belong to no such pair. $\endgroup$ – lulu Sep 29 '15 at 0:14
  • $\begingroup$ 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? $\endgroup$ – user230283 Sep 29 '15 at 0:27
  • 2
    $\begingroup$ 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$. $\endgroup$ – 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.

  • $\begingroup$ I already know, thank you! $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy