- #1
- 1,864
- 34
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!
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:
