1

In the xy-plane, how many triangles have each of their vertices at points (a,b) where a,b are integers satisfying 1 ≤ a ≤ 5 and 1≤b≤5?

I got twenty-five, but something tells me this isn't right. I set up an inequality, square root of a squared plus b squared is less than a plus b but more than the absolute value of b minus a. Squaring, we can get rid of a squared plus b squared, leaving -2ab<0<2ab, which is always true. So, each pairing works, and we have five times five for twenty-five. I feel that the answer is way too simple. If it is indeed wrong, where did I go wrong?

  • It's way too small. If one vertex is at $(1,1)$ and another is at $(2,1)$ then there are 20 choices for the third vertex --- that's 20 triangles right there, with 2 of the vertices fixed. You may have misunderstood the question (or I may have). By the way, what contest is this from? – Gerry Myerson Nov 10 '13 at 05:11
  • Why would you consider that inequality at all? It kinda looks like triangle inequality for the triangle with vertices $(0, 0), (a, 0)$ and $(a, b)$. Of course it is true. – Dan Shved Nov 10 '13 at 05:14
  • Yeah, I totally misunderstand. I thought it meant the two vertices were on the axes. (What a horrible, embarrassing mistake). This is from the 2010 Fermat II Exam of Pro2Serve at UTK. –  Nov 10 '13 at 05:15
  • Regardless, could someone help me out with the solution process and answer? –  Nov 10 '13 at 05:16
  • Hint: count the ways to choose three distinct points in ${1,2,3,4,5}^2$. Subtract the cases where the points are collinear. – mjqxxxx Nov 10 '13 at 05:28
  • @mjqxxxx, counting the number of collinear triples would seem to be the hard part of this problem. – Gerry Myerson Nov 10 '13 at 05:41
  • The sequence you get when you ask the question with 5 replaced by $n$ is tabulated at http://oeis.org/A045996 where there's a link and some formulas. – Gerry Myerson Nov 10 '13 at 05:45

2 Answers2

1

Focus on counting the ways to choose three collinear points. If the line is horizontal or vertical, then there are $5\times{{5}\choose{3}}=50$ possibilities, for a total of $100$ ways. If the slope of the line is $\pm 1$, then there are $9$ ways to place a segment containing three points, $4$ ways to place a segment containing four points (each with $2$ ways to choose the intermediate point), and one way to place a segment containing five points (with $3$ ways to choose the intermediate point), for a total of $40$ ways to choose the points with a slope of $\pm1$. If the slope is $\pm 2$ or $\pm 1/2$, then there are just $3$ ways to place a segment containing three points, for a total of $12$ with these slopes. In total there are $152$ ways to choose three collinear points.

Subtracting this from the total number of ways of choosing three points gives $$ {{25}\choose{3}}-152=2300 - 152=2148 $$ distinct triangles.

mjqxxxx
  • 41,358
0

It seems to me that it could be (25)(24)(20)/6. You start with 25 points you can choose your first point from. Then you pick any second point from any of the 24 remaining points. Then you would pick from any of the remaining 23, but you could end up with a line that way. Three points could yield a line at that point, so you actually have 20 points to choose from. But we've over-counted. There are six ways to get any of those triangles, so we divide the (25)(24)(20) by six. I'm not sure it's right, but you can check the general method with a 3x3 grid and see if it works for that.

BioBroo
  • 111