1
$\begingroup$

This problem is loosely based on the triangle inequality, which basically states that the sum of the lengths of any two sides must be greater than or qual to the length of the remaining side. The equality is achieved if the triangle is degenerate - i.e., if all the three points lie on the same line - then the sum of two shorter lengths is equal to the longer length. One can think of the triangle inequality as a restatement of "the shortest distance between two points is a line". So, here's the question again:

How many triangles are there whose sides are all positive integers and have a perimeter equal to 15?

$\endgroup$
0
$\begingroup$

By the triangle inequality that you mentioned, no side can have a length greater than half of $15$, and so all sides must be of length $7$ or less. It isn't hard to systematically brute-force all of the solutions - it turn out that there are only six of them.

  • $1,7,7$
  • $2,6,7$
  • $3,5,7$
  • $3,6,6$
  • $4,4,7$
  • $4,5,6$

Suppose we instead wanted the perimeter to be $n$, a natural number. For an algorithmic approach, start by choosing $a$, the length of the shortest side. First try $a=1$. Then $b$, the second longest side, can be no more than $a$ less than $c$, the longest side. So if $a$ is already chosen, then $b$ can be any integer between $15/2-a$ and $15/2$, by the triangle inequality. Then once you have chosen $a$ and $b$, simply let $c=15-a-b$. But be careful - if $c$ ends up smaller than $b$, you'd be double-counting, so be sure to exclude those triplets. To be safe and ensure that $c$ stays the largest side length, you should instead choose $b$ to be an integer between $15/2-a$ and $15/2-a/2$. Now we have our final algorithm:

  • Let $a=1$.
  • Let $b$ equal the smallest integer between $n/2-a$ and $(n-a)/2$, inclusive. If $b$ is less than $a$, then terminate the algorithm.
  • Let $c=n-a-b$.
  • Record the triplet $(a,b,c)$.
  • If $b$ is not the largest integer between $n/2-a$ and $(n-a)/2$ inclusive, increase it by $1$ and return to step $3$. If else, continue.
  • Increase $a$ by $1$ and return to step $2$.

This algorithm can be used to find the number of triangles with perimeter $n$ and positive integer sides, for any $n\in\mathbb N$.

Is this helpful? If my explanation is unclear, I'll be happy to clarify further.

$\endgroup$
  • $\begingroup$ Thanks for the great and quick answer! Your solution(s) were really well explained! $\endgroup$ – Jmaxmanblue Jan 13 '18 at 3:13
  • $\begingroup$ @Jmaxmanblue Good, I'm glad to hear it. $\endgroup$ – Frpzzd Jan 13 '18 at 14:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.