- #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!

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: