1
$\begingroup$

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?

$\endgroup$
  • $\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
3
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

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