Apply Generating Functions

Geometry Level 3

Find the number of distinct triplets $(a,b,c)$ integers such that $a<b<c$ and $a,b,c$ are the sides of triangle whose perimeter is $21$ .

Check out my set Some JEE problems

12 9 7 11 8 10

5 solutions

Trevor Arashiro
Feb 24, 2015

I say this is just simple counting. No fancy methods required

8,7,6

9,7,5

9,8,4

10,9,2

10,8,3

10,7,4

10,6,5

therefore, our answer is 7.

why is this lvl 5. It should be under the skill counting...

"The Algorithm" has worked; the level has descended. :) What could make this a level 5 question is if the perimeter were $2015$ instead of $21$ ; then we would need a method for such madness. We would have triplets ranging from $(2,1006,1007)$ up to $(670,672,673)$ such that $a \lt b \lt c$ and $a + b + c = 2015.$ Even better would be to find a general formula for the number of triplets for a given perimeter $N$ . Yeah, now we're talking. :D

Brian Charlesworth - 6 years, 3 months ago

Oh boy, here we go again X'D.

Id think of using the generating function, but thatd be pretty useless since we'd have to check so many cases.

Trevor Arashiro - 6 years, 3 months ago

Haha. Yeah, sorry about that. :P I've got this one on the back burner, but I do have a sense that there is a formula, (no generating functions involved).

Brian Charlesworth - 6 years, 3 months ago

@Brian Charlesworth – Wait, I'm not even sure I used the right language. I meant $(1+x+x^2+x^3...x^{670})(1+x+x^2...x^{672})$

And this is going to be one ugly formula. Because while a+b+c= 3,5,6,8 each have 1 solution, 4 has no solutions and 7,9 have 2. So it's at least a 9th degrees unction no assuming itsa polynomial.

IMO, there might not be an explicit formula. But that's no fun, there has to be one :).

Trevor Arashiro - 6 years, 3 months ago

@Trevor Arashiro – O.k., I got lazy and just googled . So for $N = 2015$ the solution would be $84840,$ but this would include triangles with two or three sides being the same length. For $N = 2015$ we would only have to worry about those with two sides the same length, so we would have to exclude triplets from $(504,504,1007)$ to $(1007,1007,1)$ , i.e., $504$ triplets. This leaves us with a final total of $84336$ . You were right about there being generating functions involved. Do you want to post the question or shall I? Or do we bother, since it may be too much to expect people to develop this formula from scratch, (although that would make it a level 9 question, methinks :) )?

Brian Charlesworth - 6 years, 3 months ago

@Brian Charlesworth – Actually, there is a formula for the number of triangles with distint integer sides and perimeter n: it's the integer closest to (n-6)^2/48 for even n and the integer closest to (n-3)^2/48 for odd n.

Otto Bretscher - 6 years, 3 months ago

@Otto Bretscher – Yes, that formula is given in the link I provided. A proof is given here .

Brian Charlesworth - 6 years, 3 months ago

@Brian Charlesworth – tnx for your link..., I learned something new about this.. :D

Ojna Eugitaraba - 6 years, 3 months ago

@Brian Charlesworth – You can post it if u like, I'm gonna be busy. I guess the generating function was right, but there apparently arent too many cases I guess.

And that formula uses the greatest integer functions and cases for even and odd, this is a great way to get around the problem i had since as I stated, we would need a 9th degree function if it were an polnomal.

Trevor Arashiro - 6 years, 3 months ago

@Brian Charlesworth – @Ojna Eugitaraba @Trevor Arashiro @Brock Brown There is a "straightforward" solution that uses the Polya enumeration technique.

Consider all sets of positive integers ${a, b, n-a-b}$ that satisfy the triangle inequality. This would be the region enclosed in $\lfloor \frac{n-1}{2} \rfloor \geq a, b \geq 1, \lfloor \frac{n-1}{2} \rfloor \geq a +b$ , and we can obtain the number of solutions using Pick's theorem. Let's say the number of lattice points is P.

Then, we could the number of points where $a = b$ or $a = n-a-b$ or $b = n-a-b$ , and say there are $3Q$ of them. The number of points where $a = b = n-a-b$ , and say there are $R$ of them.

Then, the answer will be $\frac{ P - 3Q + 2 R } { 6 }$ , because the distinct integer pairs will be repeated 6 times.

Calvin Lin Staff - 6 years, 2 months ago

Plugged into my code, it appears that if the perimeter were 2015 then the number of possible triangles would be 84336.

It would be interesting to find a general rule for N though instead of just brute forcing it.

Brock Brown - 6 years, 3 months ago

Good to get a confirmation of the $84336$ value. The link I provided does give a general formula for the scenario where the side lengths are not necessarily distinct, which is why I had to make the additional calculation. So the adjustment from the formula in the link would be to subtract the nearest integer to $\frac{N}{4}$ , where $0.5$ is rounded down.

Brian Charlesworth - 6 years, 3 months ago

Got the right answer, but I only realized about Triangle Inequality theorem after reading the comments below. Triangle Inequality theorem states that one side is always shorter than other two sides: a < b + c b < a + c c < a + b

AccelNano Lim Loong - 6 years, 3 months ago

Gamal Sultan
Feb 27, 2015

a < b < c .....................................(1)

a +b + c = 21 ............................ (2)

b -a < c < b + a ..........................(3)

From (3), (2)

2 c < 21

c < 10.5

c = 10, 9, 8

c can't be less than 8 because of (1) , (2)

The triples are

(2 , 9 ,10) ,(3 , 8 , 10) , (4 , 7, 10) , (5 , 6 , 10) , (4 , 8 , 9) , (5 , 7 , 9) , (6 , 7 , 8)

7 triples

Brock Brown
Feb 25, 2015

Nothing a little bit of Python can't solve.

from itertools import product
def triangle(a, b, c):
    return a + b > c
perimeter = 21
lengths = range(1, perimeter-1)
count = 0
for a, b in product(lengths,repeat=2):
    c = perimeter - (a + b)
    if a < b and b < c:
        if triangle(a,b,c):
            count += 1
print "Answer:", count

William Isoroku
Feb 25, 2015

Starting with $a=10$ :

We have :

$10,9,2$

$10,8,3$

$10,7,4$

$10,6,5$

Then we move to $a=9$ :

$9,8,4$

$9,7,5$

Finally, $a=8$ :

$8,7,6$

We can't go below 8, or else $b$ and $c$ would be greater than $a$ . We also cannot go above 10 or else $b+c>a$ . This defies the Triangle Inequality Theorem. So we have $7$ possible triplets.

Well didn't realized about triangle inequality theorem, I think I get the right answer by luck >.<.

AccelNano Lim Loong - 6 years, 3 months ago

Niranjan Khanderia
Feb 25, 2015

$\text{ I start with 21/2=10.5. So the c=10 and b+c=11.}\\\text{ So the triples with c=10 are (5,6,10),(4,7,10),(3,8,10),(2,9,10)............}\Large 4\\ \text{Next c=9, b+c=12. b=a=6 NO. So triples with c=9 are (5,7,9),(4,8,9)...}\Large 2\\ \text{Next c=8, b+a=13. Triples are (6,7,8).................}\Large 1 \\Total~~\boxed{\Large \color{#D61F06}{7}}$

Apply Generating Functions

5 solutions

0 pending reports