Solving Arithmetic Progression and Combinations: Question on Number Theory

Click For Summary

Homework Help Overview

The discussion revolves around a problem in number theory involving arithmetic progressions and combinations. Participants are tasked with determining the number of distinct integers that can be expressed as the sum of three different elements from a set derived from an arithmetic progression.

Discussion Character

  • Mixed

Approaches and Questions Raised

  • Participants explore the calculation of combinations from a set of 15 numbers, questioning the validity of their results and the interpretation of the problem.
  • Some participants suggest that the problem involves finding distinct sums rather than merely counting combinations, leading to discussions about the potential for repeated sums.
  • There are inquiries about how to account for the distinct sums that can be formed from the combinations of three numbers.
  • Suggestions are made to analyze the smallest and largest possible sums to better understand the range of distinct sums.

Discussion Status

The discussion is ongoing, with participants providing insights and hints to guide each other toward a better understanding of the problem. Some have proposed methods to simplify the problem by reducing the set size or focusing on the sums rather than combinations. There is no explicit consensus yet, but productive lines of reasoning are being explored.

Contextual Notes

Participants note the challenge of ensuring that distinct integers are counted without repetition, and there is an acknowledgment of the complexity introduced by the nature of sums formed from distinct elements.

hms.tech
Messages
246
Reaction score
0

Homework Statement



see attachment

Homework Equations



Combinations and Arithmetic progression formulae

Nth term = 4+(N-1)(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
 

Attachments

  • Question.PNG
    Question.PNG
    13.3 KB · Views: 437
Physics news on Phys.org
hms.tech said:

Homework Statement



see attachment

Homework Equations



Combinations and Arithmetic progression formulae

Nth term = 4+(N-1)(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

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:
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.
 
Petek said:
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.

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?
 
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:
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?
 
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".
 
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?
 
haruspex said:
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?

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
hms.tech said:
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 .

Bingo.
 

Similar threads

  • · Replies 1 ·
Replies
1
Views
2K
Replies
3
Views
2K
Replies
3
Views
2K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 5 ·
Replies
5
Views
3K
  • · Replies 5 ·
Replies
5
Views
4K
  • · Replies 7 ·
Replies
7
Views
2K
  • · Replies 3 ·
Replies
3
Views
1K
  • · Replies 4 ·
Replies
4
Views
2K