1. Not finding help here? Sign up for a free 30min 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!

Question on Number theory

  1. Jan 4, 2013 #1
    1. The problem statement, all variables and given/known data

    see attachment

    2. Relevant equations

    Combinations and Arithmetic progression formulae

    Nth term = 4+(N-1)(3)

    3. The attempt at a solution

    After recognizing that this is an arithmetic progression, I calculated the number of terms as : 15

    Then , as we have to find out, in simple terms, the number of sets of three different numbers from these 15 numbers .

    I applied the combinations rule :

    15!/(3!*12!)

    But the answer is clearly not among any of the choices.

    Please help explain to me where did I go wrong and also recommend me some sources (or topics) I could study to solve such questions.

    Thanks
     

    Attached Files:

  2. jcsd
  3. Jan 4, 2013 #2

    Mark44

    Staff: Mentor

    I can't see anything wrong with what you did. There are 15 numbers in the set, and you're looking for all combinations taken 3 at a time, which I work out to 455.

    Edit: I must have missed something here...
     
    Last edited: Jan 4, 2013
  4. Jan 4, 2013 #3
    You are being asked to find the number of integers that can be expressed as the sum of three distinct elements of the set. That's not the same as finding the number of subsets consisting of three elements. You can have an integer that's the sum of three distinct elements in more than one way. For example,

    48 = 4 + 16 + 28 = 7 + 19 + 22

    You have to find a way to take this into account.
     
  5. Jan 4, 2013 #4
    Just a tip on the above:

    Assume an integer is expressible as the sum of three distinct integers from this set, namely 3x+1, 3y+1 and 3z+1, which makes 3x+3y+3z+3. Assuming a,b,c also satisfy this, it follows x+y+z=a+b+c. For example, 7+10+13=30 corresponds to 2+3+4=9 as the first sum, so 1+3+5 will also satisfy the relation: 4+10+16=30.

    Long story short, the sum you want here depends on the sum x+y+z, not on x,y and z individually. Can you think of a way to take this into account?
     
  6. Jan 4, 2013 #5
    Even with that in mind, I have absolutely nothing to ensure that I don't take repeat integers (like petek mentioned above)

    Would you point out the way to do this ?

    @millineal, I understand what you just told me but I still can't seem to find a way to make a breakthrough... :(
     
    Last edited: Jan 4, 2013
  7. Jan 4, 2013 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Millennial is suggesting you equate the problem to another on a set of smaller numbers. I.e. instead of dealing with {3x+1} deal with just {x}. Next, think about the smallest and largest sums you can make by summing triplets. That puts an upper bound on the number of sums you can make. Are there any in that range you can't make?
     
  8. Jan 4, 2013 #7

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    While there are 455 different combinations, there are far, far fewer distinct sums. The correct answer is not "none of the other answers is correct".
     
  9. Jan 4, 2013 #8

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Hint: What are the smallest and largest sums that can be constructed? Just from this, you should see that there's no way that the answer is 455. What's the maximum possible number of sums, just based on the smallest and largest sums and the relation between consecutive elements in the set?
     
  10. Jan 5, 2013 #9
    Well, that simplifies things.

    After working out what you said I conclude that the answer is 37.

    And no, there are no terms in the range that I can't make .
     
  11. Jan 5, 2013 #10

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Bingo.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Question on Number theory
  1. Number Theory Question (Replies: 1)

  2. Number Theory question (Replies: 2)

Loading...