Author |
Topic: Cousins of the Triangular Numbers (Read 834 times) |
|
ecoist
Senior Riddler
Gender: 
Posts: 405
|
 |
Cousins of the Triangular Numbers
« on: Nov 24th, 2006, 9:05pm » |
 Quote  Modify
|
The triangular numbers are the number of points in a triangular array of points. For example, the arrangement of ten bowling pins is a triangular array with four pins on a side. Thus 10 is a triangular number. For triangular arrays with n-1 points on a side, The numbers C(n,2) are the triangular numbers, where C(n,k) denotes the number of k-subsets of an n-set.
If, in a triangular array with n points on a side, you count the number of triples of points which are vertices of equilateral triangles with sides parallel to the sides of the array, then that number is C(n+1,3). (Maybe this number should be called a tetrahedral number because it is also the number of cannon balls in a tetrahedral array of cannon balls with n-1 balls on a side.)
Now, if, you drop the parallel restriction, then the number of all triples of points in a triangular array which are vertices of equilateral triangles, you get the number C(n+2,4)! Why is that?
|
| « Last Edit: Nov 26th, 2006, 3:43pm by ecoist » |
 IP Logged |
|
|
|
checker
Newbie
Posts: 44
|
|
Re: Cousins of the Triangular Numbers
« Reply #1 on: Nov 24th, 2006, 9:15pm » |
Quote Modify
|
can you tell me what is the subject of the problem is it dealing in sets or matrixes or ........
|
|
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Cousins of the Triangular Numbers
« Reply #2 on: Nov 25th, 2006, 4:27pm » |
Quote Modify
|
Just the last paragraph, checker. For n=3, the triangular array looks like (used "_" instead of a space to get the spacing right):
__1
_2_3
4_5_6
The last paragraph says the number of triples of points in the above array which are the vertices of equilateral triangles is C(3+2,4)=5. This is correct because all such triples are {1,2,3}, {2,4,5}, {3,5,6}, {1,4,6}, and {2,3,5}.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Cousins of the Triangular Numbers
« Reply #3 on: Nov 25th, 2006, 5:05pm » |
Quote Modify
|
The subject of the problem is the triangular numbers. I take it from your question, checker, that you are confused by the term "array". While "array" is used in computing to refer to what mathematicians call a "matrix", that is not what ecoist meant. In common english, "array" means "an organized arrangement", and that is what ecoist means. Points placed in a nice regular pattern - in this case, forming triangles. The number of points in the arrangements are the triangular numbers:
.
The first triangular number is 1.
.
. .
The second triangular number is 3.
.
. .
. . .
The third triangular number is 6.
.
. .
. . .
. . . .
The fourth triangular number is 10.
It should be fairly easy to see that the nth triangular number is 1 + 2 + 3 + ... + n = n(n+1)/2.
The values C(n, k) are just the binomial coefficients, given by Pascal's triangle, or the formula C(n, k) = n!/k!(n-k)!. They are more normally expressed with n placed above k and surrounded by large parentheses, but the limitations of this forum don't allow that notation, so we use C(n, k) instead.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Cousins of the Triangular Numbers
« Reply #4 on: Nov 25th, 2006, 5:26pm » |
Quote Modify
|
I've had my own problems interpreting this puzzle, though, because ALL of the sub-triangles ecoist is refering to have sides parallel to the sides of the large triangles. Using his example: {2,3,5} is the one "non-parallel" triangle picked up, but in fact 2-3 is parallel to 4-6, 2-5 is parallel to 1-6, and 3-5 is parallel to 1-4.
C(n+1, 3) is the number of sub-triangles that "point" in the same direction as the original triangle. C(n+2,4) is the number of all sub-triangles (including those that point opposite the original triangle).
|
| « Last Edit: Nov 25th, 2006, 5:27pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Cousins of the Triangular Numbers
« Reply #5 on: Nov 25th, 2006, 8:24pm » |
Quote Modify
|
Thanks, Icarus, for clarifying the issues. I failed to notice that "sides parallel" was not sufficient. I should have said something like what you said, "point the same way".
Also, how did you get the dots arranged so well? I failed miserably.
As soon as you get to triangular arrays with more than 3 points on a side, there are triples of points which are vertices of an equilateral triangle with no sides parallel to the sides of the array.
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Cousins of the Triangular Numbers
« Reply #6 on: Nov 25th, 2006, 8:47pm » |
Quote Modify
|
on Nov 25th, 2006, 8:24pm, ecoist wrote:
Also, how did you get the dots arranged so well? I failed miserably. |
|
You gotta be a moderator+uberpuzzler for that uber cool power.
-- AI
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Cousins of the Triangular Numbers
« Reply #7 on: Nov 25th, 2006, 10:51pm » |
Quote Modify
|
on Nov 25th, 2006, 8:47pm, TenaliRaman wrote:
You gotta be a moderator+uberpuzzler for that uber cool power.
-- AI |
|
Or some seniority 
.
. .
. . .
. . . .
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Cousins of the Triangular Numbers
« Reply #8 on: Nov 25th, 2006, 11:26pm » |
Quote Modify
|
on Nov 25th, 2006, 10:51pm, Sameer wrote:
Or some seniority
|
|
Oh you mean this  ,
.
. .
. . .
. . . .
-- AI
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Cousins of the Triangular Numbers
« Reply #9 on: Nov 26th, 2006, 2:08am » |
Quote Modify
|
The easiest is to steal the code behind the posting by using the Quote option. You can make it very simply in any size without any seniority:
.
. .
. . .
. . . .
. . . . .
. . . . . .
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Cousins of the Triangular Numbers
« Reply #10 on: Nov 26th, 2006, 12:03pm » |
Quote Modify
|
A great trick for finding out how someone did something is, as jollytall mentions, to Quote their post. You will see the coding for the post in its entirety, except that any quotes in that post are removed (YaBB doesn't do nested quotes).
What I and the others did was use the [ pre ] [ /pre ] tags for "preformatted text". This switches to a fixed-width font, and stops your browser from reformatting the text (in particular, from collapsing multiple spaces). Unfortunately, it doesn't seem to stop YaBB from doing its own reformatting when it creates the html code, so you still end up with YaBB removing spaces it thinks are unneeded. I think 5 spaces is the max YaBB will allow in a row without collapsing.
Alternatively to the [ pre ] tag, you can also use the [ tt ] [ /tt ] tag, or change to a fixed-width font directly using the [ font=.... ] [ /font ] tag. One problem with using the [ pre ] or [ tt ] tags is that they also switch the font size to 1, so you end up with tiny characters. I usually switch it back to 2 or 3 inside (depending on which size I think looks better in that instance). Font sizes run from 1 to 6, I believe (I experimented a few years ago to find them, but my memory may not be right). For this reason, if you quote my post, you will see [ pre ][ size=3 ] ....
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Cousins of the Triangular Numbers
« Reply #11 on: Nov 26th, 2006, 12:09pm » |
Quote Modify
|
on Nov 25th, 2006, 8:24pm, ecoist wrote:| As soon as you get to triangular arrays with more than 3 points on a side, there are triples of points which are vertices of an equilateral triangle with no sides parallel to the sides of the array. |
|
True. As soon as you can fit a hexagon of points, you can choose triangles consisting of 3 non-adjacent vertices from the hexagon. I take it that C(n+2, 4) counts these as well?
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Cousins of the Triangular Numbers
« Reply #12 on: Nov 26th, 2006, 2:40pm » |
Quote Modify
|
Quote:| True. As soon as you can fit a hexagon of points, you can choose triangles consisting of 3 non-adjacent vertices from the hexagon. I take it that C(n+2, 4) counts these as well? |
|
Yes.
|
|
IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Cousins of the Triangular Numbers
« Reply #13 on: Nov 27th, 2006, 1:22pm » |
Quote Modify
|
on Nov 26th, 2006, 12:03pm, Icarus wrote:| A great trick for finding out how someone did something is, as jollytall mentions, to Quote their post. |
|
yes, that is what you learn by staying long here too!! 
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Cousins of the Triangular Numbers
« Reply #14 on: Nov 27th, 2006, 5:32pm » |
Quote Modify
|
I'd like this thread to get back on track, so I am going to tackle the easier result: The number of "aligned" subtriangles is given by C(n+1,3).
Recall from Pascal's triangle that C(n+1,k) = C(n,k) + C(n,k-1).
Let Tn = C(n+1,2) be the nth triangular number, and let An (n>1) be the nth "aligned" number - i.e., the number of subtriangles aligned with the main triangle.
We note that A2 = 1 = C(3,3). We note that if we add a new row to the bottom of the triangle, all the aligned triangles involving a point on the bottom must in fact include 2 such points, and have a point in the original triangle as the third vertex. Conversely, every point of the original triangle is the vertex of exactly one such aligned triangle. Thus any aligned subtriangle of the larger triangle is either also a subtriangle of the original, or else one of the Tn triangles with a one vertex in the original. That is, An+1 = An + Tn. If we assume that An = C(n+1,3), then An+1 = C(n+1,3) + C(n+1,2) = C(n+2,3).
Hence An = C(n+1,3) for all n by induction.
|
| « Last Edit: Nov 27th, 2006, 5:33pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Cousins of the Triangular Numbers
« Reply #15 on: Nov 27th, 2006, 10:07pm » |
Quote Modify
|
Well, going along the lines of Icarus' solution,
we can solve the original problem like this, right?
An+1 = C(n+2,4)+C(n+1,2)+\sum_{i<=n,i odd} (n-i)
However, i am not able to reduce it to C(n+3,4). I will check it again, once i am done waking up fully.
-- AI
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Cousins of the Triangular Numbers
« Reply #16 on: Nov 28th, 2006, 1:14am » |
Quote Modify
|
Let Xn denote the total number of equilateral triangles containd in the n-th triangular array Tn. Then Yn = Xn - Xn-1 is the number of such triangles which contain at least one vertex on the bottom row. Similarly, Zn = Yn - Yn-1 is the number of such triangles that contain at least one vertex on the bottom edge and one on the upperleft-most edge. It suffices to show Zn = C(n,2), for then
Yn = Z2 + Z3 + ... + Zn = C(2,2) + C(3,2) + ... + C(n,2) = C(n+1,3),
and Xn = Y2 + ... + Yn = C(3,3) + C(4,3) + . . . + C(n+1,3) = C(n+2,4).
We exhibit a bijection between the triples counted by Zn, and the poins of Tn-1.
Let w denote the complex number e2pi i/6 = 1/2 + i sqrt(3)/2, so that we can write
Tn = { x+y*w | x,y integers, 0 < x,y < x+y < n}.
Now for two distinct points a,b, there are two values of c for which {a,b,c} is equilateral, given by
c = a + w+/-1*(b-a).
So suppose x is a point on the bottom row of Tn, and yw is a point on the upperleft row. Then 0< x,y < n. Since w2 = w - 1, we have
x + w(yw-x) = x + y(w-1) - wx = x-y + (y-x)w,
which lies in Tn iff x=y, for otherwise either x-y or y-x will be negative. So we have the triples {t, t*w, 0}, where 0 < t < n. The other vertex
x + w-1(yw-x) = x + y - x(1-w) = y + xw
lies in Tn iff x+y < n. So we have the triples {x, yw, y+xw}, where 0< x,y < x+y < n. Note that this contains the above triples in the cases x=0 or y=0. Also, we may assume x>0, since {0, yw, y} = {y, 0w, 0+yw}.
Then {x, yw, y+xw} <-> y+xw is a bijection between triples counted by Zn, and the points of Tn-1, viewed as Tn minus the bottom row.
Interesting: We've shown that each point of Tn-1 is in a unique equilateral triangle with one point on the bottom row of Tn and the other on the upperleft row. (Is this obvious?). On the other hand, it's obvious that each point of Tn-1 is in a unique equilateral triangle with both other points on the bottom row of Tn, and there are clearly C(n,2) of each.
|
|
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Cousins of the Triangular Numbers
« Reply #17 on: Nov 28th, 2006, 2:40pm » |
Quote Modify
|
Quote:| Interesting: We've shown that each point of Tn-1 is in a unique equilateral triangle with one point on the bottom row of Tn and the other on the upperleft row. (Is this obvious?). |
|
I don't know how obvious this is, but one way of looking at it is as follows. Let a be any point, not on the right edge of the array, of an equilateral triangle with b on the bottom edge and c on the left edge. There is a unique equilateral triangle with bottom coincident with the bottom edge of the array, left edge coincident with the left edge of the array, and third edge coincident with a. Since the combination of these two triangles has 3-fold symmetry, b and c are uniquely determined images of a under this symmetry. Beautiful solution, Eigenray!
Another way of looking at this problem involves inclusion-exclusion. Xn counts all those triangles with all points on all three edges of the array plus all those in the union those triangles having no point on the bottom edge, those triangles having no point on the left edge, and those triangles having no point on the right edge. Hence, using inclusion-exclusion, we get the recursion
Xn=n-1+3Xn-1-3Xn-2+Xn-3.
Xn=C(n+2,4) satisfies this recursion.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print