Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: For each positive integer n, let T(n) be the number of triangles with

  1. Apr 23, 2010 #1
    1. The problem statement, all variables and given/known data

    For each positive integer n, let T(n) be the number of triangles with integer side lengths, positive area, and perimeter n. For example, T(6) = 1 since the only such triangle with a perimeter of 6 has side lengths 2, 2 and 2.

    (a) Determine the values of T(10), T(11) and T(12).

    (b) If 'm' is a positive integer with m >= 3, prove that T(2m) = T(2m-3)

    (c) Determine the smallest positive integer 'n' such that T(n) > 2010.

    Some time ago I wrote a math contest and this one question has been bugging me for some time. I wondering if I could ask for some guidance to point me in the general direction.

    2. Relevant equations

    Who knows?

    Perhaps the triangle inequality, but I'm not sure if that counts as an equation.

    3. The attempt at a solution

    I'm looking at this question and I have absolutely no idea where to start, so this is just me brainstorming and trying my best. For all I know, I'm probably completely off, any tips to get me on the right direction would be much appreciated!

    So I thought I should at least set a scheme for the way I'm going to label my triangle... since a triangle with side lengths 4 ,3 ,3 is the same as the triangle with side lengths, 3, 4 ,3 it seems logical to write:

    S1 >= S2 >= S3

    It dawned on me that if I could find the range of possible values, I could potentially find all the possible combinations of said values and then subtract the number of invalid combinations. I think I'm making it a little more complicated than it needs to be, but this is my only lead so here goes:

    From the triangle inequality, the sum of any two side lengths must be greater than the remaining side (if it is equal the triangle becomes a line), so for any valid triangle the greatest side must be < n/2 (half of the perimeter) else I will not even get a triangle at all so...

    S1 < n/2

    And to get the lower range I looked at my established restriction of S1 < n/2, which would leave the best case scenario for the other two side lengths to be n/4, which would still result in a line... so I think I can conclude:

    S3 > n/4

    At this point, it is possible to figure out the range (which I will let r represent) of values from the upper range - the lower range (n/2 - n/4), which would let me model all the possible types of triangles with side lengths within that range as a combination with repetition. Little rusty from an old data lesson, but I think the formula goes like this:

    (r + 3 - 1)! / [(3!)(r - 1)!] ; where r is the range of possible values...

    As far as I know, this works with T(6) because there are no invalid triangles. i.e.,

    Upper range: 6 / 2 = 3
    Lower range: 6 / 4 = 1.5 = 1 (round down because it represents value that is not a valid side length)
    Range (r): 3 - 1 - 1 = 1 (we subtract one because the lower range is not a valid side length)
    Possible triangles: (1 + 3 - 1)! / [(3!)(1-1)!] = 1

    And according to the question, the answer is in fact 1, but this only works because the only combination of side lengths possible is 2,2,2 - that is, there are no invalid combinations. This is where I am stuck; how would I find the number of invalid combinations so I could subtract it from the total number of combinations possible?

    Actually, my main problem is whether it is even possible to model that as a function. I think I am wasting my time and there is probably a very simple solution, but I cannot seem to find one. If anyone can give me a nudge in the right direction it'd be much appreciated... this thing is making me lose sleep!
    Last edited: Apr 23, 2010
  2. jcsd
  3. Jul 5, 2010 #2
    I myself wrote the Euclid and recall this being question 10. I remember doing a) simply by counting out the possible triangles. I read about the problem later online and although I'm unable to say whether your factorial approach is correct I have not seen it anywhere.

    Here are some useful links if you'd like to read:
    • The technical definition: http://mathworld.wolfram.com/IntegerTriangle.html
    • A really interesting approach: http://susam.in/downloads/mathematics/theorems/integer-triangles-with-fixed-perimeter.pdf [Broken] because it takes advantage of the two triangle inequalities I'm sure you know; that if a <= b <= c, then a + b > c.
    • Here is the beginning of a journal paper: http://www.jstor.org/pss/3219089. It may also be useful to you.

    I hope that helps!
    Last edited by a moderator: May 4, 2017
  4. Jul 14, 2010 #3
    Thanks! Amazing stuff :D
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook