Posted by: Dave Richeson | February 10, 2011

Counting triangles on a tin ceiling (solution, take 2)

This is the solution to a problem I posed in my previous blog post. Please read that post first.

[Update: I posted a solution to this problem two days ago. Yesterday Brent Yorgey pointed out that my analysis of “type 2″ triangles was not quite correct. (See his comment below.) So I went back to the whiteboard and worked out the correct solution. Hopefully the formula given below is correct. Thanks, Brent!]

Here’s a recap of the problem: How many triangles are there in an {n\times n} grid of squares with X’s through them (as shown below)?

We realized that there are two types of triangles. We’ll say a triangle is of “type 1″ if the legs of the triangle run horizontally and vertically (as shown below).

A triangle is of “type 2″ if the hypotenuse runs either horizontally or vertically (as shown below).

Type 1

Consider the type 1 triangles with {k} horizontal (or vertical) segments in each leg. Examples of {k=1, 2, 3} are shown in the diagram. When {k=1} there are {4n^{2}} such triangles in the ceiling. In particular, there are {n^{2}} having the orientation shown, but then they can be rotated 90, 180, or 270 degrees. When {k=2} there are {4(n-1)^{2}} such triangles. When {k=3} there are {4(n-2)^{2}}, etc. Thus, the total number of type 1 triangles is

\displaystyle \sum_{i=1}^{n}4i^{2}=\frac{4 n(n+1)(2n+1)}{6}.

Type 2

Counting the type 2 triangles is tricker. Let {k} denote the number of segments in the hypotenuse of the triangle. Examples of {k=1,2,3} are shown in the diagram. The key observation is that each time {k} increases by one unit the horizontal distance (in the given configuration) increases by a half unit.

For example, when {n=4} here are the number of type 2 triangles of a given orientation for the possible values of {k} (so the final count will be four times the sum of these).

\displaystyle \left.\begin{array}{|c|c|c|c|}\hline k & \text{up-and-down} & \text{left-to-right} & \text{total}\\ \hline 1 & 4 & 4 & 4\cdot 4\\ \hline 2 & 3 & 4 & 3\cdot 4\\ \hline 3 & 2 & 3 & 2\cdot 3\\ \hline 4 & 1 & 3 & 1\cdot 3\\ \hline \end{array}\right.

And here are the number when {n=5}.

\displaystyle \left.\begin{array}{|c|c|c|c|}\hline k & \text{up-and-down} & \text{left-to-right} & \text{total}\\ \hline 1 & 5 & 5 & 5\cdot 5\\ \hline 2 & 4 & 5 & 4\cdot 5\\ \hline 3 & 3 & 4 &3\cdot 4\\ \hline 4 & 2 & 4 & 2\cdot 4\\ \hline 5 & 1 & 3 & 1\cdot 3\\ \hline \end{array}\right.

In general, for a given {n} and {k} and a given orientation we can fit {n-k+1} triangles in one direction and {n-\lceil\frac{k}{2}\rceil+1} in the other. Thus the number of type 2 triangles is

\displaystyle 4\sum_{k=1}^{n}\big((n-k+1)(n-\Big\lceil\frac{k}{2}\Big\rceil+1)\big).

It follows that there is a different closed form for this summation for {n} even and {n} odd.

Consider the case that {n} is even. I’ll skip most of the algebraic details, but essentially I summed the values for even {k} and odd {k} separately.

\displaystyle 4\sum_{k=1}^{n}\big((n-k+1)(n-\Big\lceil\frac{k}{2}\Big\rceil+1)\big).

\displaystyle =4\sum_{i=1}^{\frac{n}{2}}\big((2i-1)(\frac{n}{2}+i)+(2i)(\frac{n}{2}+i)\big)

\displaystyle =16\sum_{i=1}^{\frac{n}{2}}i^{2}+(8i-4)\sum_{i=1}^{\frac{n}{2}}i-2n\sum_{i=1}^{\frac{n}{2}}1

\displaystyle =\frac{10n^{3}+15n^{2}+2n}{6}.

Now suppose {n} is odd.

\displaystyle 4\sum_{k=1}^{n}\big((n-k+1)(n-\Big\lceil\frac{k}{2}\Big\rceil+1)\big).

\displaystyle =4\sum_{i=1}^{\frac{n+1}{2}}\big((2i-1)(\frac{n-1}{2}+i)\big)+4\sum_{i=1}^{\frac{n-1}{2}}\big((2i)(\frac{n+1}{2}+i)\big)

\displaystyle =16\sum_{i=1}^{\frac{n+1}{2}}i^{2}+(8i-4)\sum_{i=1}^{\frac{n+1}{2}}i-2(n-1)\sum_{i=1}^{\frac{n+1}{2}}1-4(n+1)^{2}

\displaystyle =\frac{10n^{3}+15n^{2}+2n-3}{6}.

Adding the number of type 1 and type 2 triangles and simplifying the expression we find that the total number of triangles in an {n\times n} grid is

\displaystyle \frac{6n^{3}+9n^{2}+2n}{2}

when {n} is even and

\displaystyle \frac{6n^{3}+9n^{2}+2n-1}{2}

when {n} is odd.

Thus, here are the number of triangles for the first few {n}-values:

\displaystyle \left.\begin{array}{|c|c|}\hline n & \text{number of triangles} \\\hline 1 & 8 \\\hline 2 & 44 \\\hline 3 & 124 \\\hline 4 & 268 \\\hline \end{array}\right.

In particular, there are 268 triangles in the {4\times 4} example at the start of the blog post.

When I posted my first solution I claimed that this sequence was not in the On-line Encyclopedia of Integer Sequences database. Now that I’ve corrected the formula (and hence the fourth term of the sequence), I discovered that it is already there!. (They give more terms of sequence A100583: 8, 44, 124, 268, 492, 816, 1256, 1832, 2560, 3460, 4548, 5844, 7364, 9128, 11152, 13456, 16056, 18972, 22220, 25820, 29788, 34144, 38904, 44088, 49712, 55796, 62356, 69412, 76980, 85080, 93728, 102944, 112744, 123148, 134172, 145836.)

About these ads

Responses

  1. […] I’ll end this blog post here in case you want to think about the problem yourself. I’ll give our solution in my follow-up post. […]

  2. I don’t think your analysis of type 2 triangles is quite right. Every time you increase the hypotenuse of a type 2 triangle by 1 unit, the width (given the orientation you illustrated for type 2) only increases by 1/2 unit, so there are not always i(i-1) of them. The number of triangles that will fit from top-bottom decreases by 1 each time, but the number of triangles that fit left-right only decreases by 1 every OTHER time. For example, in the 4×4 grid shown, you can see that there are actually 3 (not 2) type 2 triangles with a hypotenuse of 4.

    This makes things a bit trickier (although it does mean that the first case is actually not a special case!). I think the correct formula for the number of type 2 triangles is

    \displaystyle 4 \sum_{i=1}^n (n - i + 1) (n - \left\lceil\frac{i}{2} \right\rceil + 1)

    although I am not sure of a nice way to simplify this off the top of my head.

  3. Of course, I meant to say, 12 type 2 triangles with a hypotenuse of 4, three in each orientation.

    • Ugh! Thanks, Brent. You are definitely correct about our mistake. Clearly I should have waited more than 20 minutes before typing up and publishing our “result” :-) I’m going to pull this off my blog temporarily until I can find a fix (or determine that there isn’t an elegant one).

    • Check it out now. I think it is fixed.

      • Looks good to me! You ought to submit a link to this blog post to be included in the OEIS entry.

  4. I’m not sure about a closed form, but in counting triangles of Type 2, we can do the following. The number of triangles with hypotenuse on a particular vertical line is T(n), except for those that don’t fit in the n x n grid, which is easily seen to be A002623, the partial sum of alternate triangular numbers. Thus, {the number of triangles of type 2} = 4 n T(n) – {the (n-2)th term of A002623).

  5. Beautiful problem and an elegant solution, although i think we can count total number of triangles using coordinates of the points. I will think on this problem and as soon as I will post it in my blog. I have another problem on combinatorics, please help.
    “THERE ARE 10 BOYS STANDING IN A QUEUE FOR A TICKET WORTH 5 RS. 5 OF THEM HAVING 5 RS NOTE AND 5 OF THEM HAVING 10 RS NOTE. IN HOW MANY WAYS THEY CAN STAND IN THE QUEUE SUCH THAT NONE HAVE TO WAIT FOR A CHANGE( THE SALESMAN DO NOT HAVE ANY MONEY TO BEGIN WITH). You can change RS with $ if you wish.


Categories

Follow

Get every new post delivered to your Inbox.

Join 222 other followers

%d bloggers like this: