2

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? –  Sep 29 '15 at 00:08
  • Yes. But don't forget that some elements in your progression belong to no such pair. – lulu Sep 29 '15 at 00: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? –  Sep 29 '15 at 00:27
  • 2
    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 00:33
  • ..or we can make a stronger statement there must be two distinct pairs that add to 104. – fleablood Feb 17 '16 at 16:09

2 Answers2

3

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.

Rohcana
  • 449
1

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

Benjamin Dickman
  • 14,451