Problem of distinct integers chosen from the arithmetic progression

  • #1
disregardthat
Science Advisor
1,854
33
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 [itex]A[/itex] be any set of [itex]20[/itex] distinct integers chosen from the arithmetic progression [itex]1,4,7,...,100[/itex]. Prove that there must be two distinct integers in [itex]A[/itex] whose sum is [itex]104[/itex]."

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

This sequence has [itex]34[/itex] members, (As [itex]3 \cdot 34-2=100[/itex])

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

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

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

This leaves us with the [itex]16[/itex] solutions [itex](2,34),(3,33),...,(17,19)[/itex]

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

Appreciate if someone had a look!
 
Last edited:

Answers and Replies

  • #2
836
13
Looks good to me-great stuff! What are these 'putnam problems'? They sound very interesting.
 
  • #3
disregardthat
Science Advisor
1,854
33
Thanks,
Search putnam problems in google.

There is a contest named putnam which is known for it's hard math problems, and is arranged every year.
 

Related Threads on Problem of distinct integers chosen from the arithmetic progression

  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
2
Views
2K
Replies
4
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
4
Views
6K
Replies
1
Views
2K
Replies
17
Views
1K
Replies
5
Views
2K
  • Last Post
Replies
15
Views
3K
Top