1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Problem of distinct integers chosen from the arithmetic progression

  1. Feb 26, 2008 #1


    User Avatar
    Science Advisor

    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]."

    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: Feb 26, 2008
  2. jcsd
  3. Feb 26, 2008 #2
    Looks good to me-great stuff! What are these 'putnam problems'? They sound very interesting.
  4. Feb 26, 2008 #3


    User Avatar
    Science Advisor

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook