# Homework Help: Question on Number theory

1. Jan 4, 2013

### hms.tech

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

File size:
30.8 KB
Views:
119
2. Jan 4, 2013

### 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
3. Jan 4, 2013

### Petek

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.

4. Jan 4, 2013

### Millennial

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?

5. Jan 4, 2013

### hms.tech

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
6. Jan 4, 2013

### haruspex

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?

7. Jan 4, 2013

### D H

Staff Emeritus
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".

8. Jan 4, 2013

### D H

Staff Emeritus
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?

9. Jan 5, 2013

### hms.tech

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 .

10. Jan 5, 2013

### haruspex

Bingo.

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook