# Problem of distinct integers chosen from the arithmetic progression

1. Feb 26, 2008

### disregardthat

I have a solution to a problem which I am not certain that is complete. (It's a putnam problem so I can't believe I solved it) Would you mind to take a look at it?

The problem stated:
"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$."

Solution:
The arithmetic sequence $u=1,4,7,...,100$ can generally be described as $u_n=3n-2$, where $n$ is the $n$'th member of the sequence $u$.

This sequence has $34$ members, (As $3 \cdot 34-2=100$)

The set $A$ is the set of $20$ chosen distinct integers of the sequence $u$.
We shall prove that there is at least $2$ distinct integers in $A$ such that their sum is $104$.

Consider the set $B =\{ u_1,u_2,...,u_{34} \} \Rightarrow A \subset B$. Now, we can achieve set $A$ by eliminating $14$ elements of set $B$.

Consider the elements of $B$, $u_r$ and $u_k, r \not = k$. For their sum to be $104$,
$u_r+u_k=104 \Rightarrow 3r-2+3k-2=104 \Rightarrow 3(r+k)=108 \Rightarrow r+k=36$.
This equation has $33$ solutions, namely $(r,k) = (2,34),(3,33),...,(34,2)$, but only $17$ distinct solutions, $(2,34),(3,33),...,(18,18)$. The solution $(18,18)$ necessarily means that $u_r=u_k$ which is impossible as $r \not = k$.

This leaves us with the $16$ solutions $(2,34),(3,33),...,(17,19)$

To achieve set $A$, we eliminate $14$ elements from $B$. The maximum amount of pairs we can demolish is then $14$ (one element from each pair). This leaves us with at least $2$ pairs that sum up to $104$ in any set $A$, which of course means that there is two distinct integers in $A$ that sum up to $104$.

Appreciate if someone had a look!

Last edited: Feb 26, 2008
2. Feb 26, 2008

### qspeechc

Looks good to me-great stuff! What are these 'putnam problems'? They sound very interesting.

3. Feb 26, 2008

Thanks,