Problem of distinct integers chosen from the arithmetic progression

In summary, the conversation discusses a solution to a Putnam problem which involves proving that in a set of 20 distinct integers chosen from an arithmetic sequence, there must be two integers whose sum is 104. The solution uses the fact that the sequence has 34 members and eliminates 14 elements to show that there are at least 2 pairs in the set that sum up to 104. The conversation also mentions the Putnam contest, known for its difficult math problems.
  • #1
disregardthat
Science Advisor
1,866
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 [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:
Mathematics news on Phys.org
  • #2
Looks good to me-great stuff! What are these 'putnam problems'? They sound very interesting.
 
  • #3
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.
 

1. What is the "Problem of distinct integers chosen from the arithmetic progression"?

The "Problem of distinct integers chosen from the arithmetic progression" is a mathematical problem that involves selecting a certain number of distinct integers from an arithmetic progression. An arithmetic progression is a sequence of numbers where the difference between each consecutive number is the same.

2. What is an example of the "Problem of distinct integers chosen from the arithmetic progression"?

An example of this problem would be selecting 3 distinct integers from the arithmetic progression 1, 4, 7, 10, 13. The possible combinations of distinct integers would be (1,4,7), (1,4,10), (1,4,13), (1,7,10), (1,7,13), (1,10,13), (4,7,10), (4,7,13), (4,10,13), (7,10,13).

3. What is the significance of this problem in mathematics?

This problem has applications in various mathematical concepts such as combinatorics, number theory, and algebra. It also has connections to other problems such as the subset sum problem and the knapsack problem.

4. What is the formula for calculating the number of distinct integers chosen from an arithmetic progression?

The formula for calculating the number of distinct integers chosen from an arithmetic progression is nCr, where n is the number of terms in the progression and r is the number of distinct integers to be chosen. In the example given earlier, n = 5 and r = 3, so the number of distinct integers chosen would be 5C3 = 10.

5. What are some real-world applications of the "Problem of distinct integers chosen from the arithmetic progression"?

This problem has applications in areas such as coding theory, cryptography, and data compression. It also has practical uses in computer science for generating unique IDs or passwords, and in finance for calculating compound interest and loan repayment schedules.

Similar threads

  • General Math
Replies
4
Views
3K
  • Precalculus Mathematics Homework Help
Replies
1
Views
884
Replies
9
Views
1K
  • General Math
Replies
1
Views
3K
  • Precalculus Mathematics Homework Help
Replies
2
Views
2K
  • Precalculus Mathematics Homework Help
Replies
2
Views
920
  • Precalculus Mathematics Homework Help
Replies
4
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
3K
  • Precalculus Mathematics Homework Help
Replies
4
Views
2K
  • Precalculus Mathematics Homework Help
Replies
5
Views
2K
Back
Top