|
||
|
Title: Cousins of the Triangular Numbers Post by ecoist on Nov 24th, 2006, 9:05pm 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? |
||
|
Title: Re: Cousins of the Triangular Numbers Post by checker on Nov 24th, 2006, 9:15pm can you tell me what is the subject of the problem is it dealing in sets or matrixes or ........ |
||
|
Title: Re: Cousins of the Triangular Numbers Post by ecoist on Nov 25th, 2006, 4:27pm 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}. |
||
|
Title: Re: Cousins of the Triangular Numbers Post by Icarus on Nov 25th, 2006, 5:05pm 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. |
||
|
Title: Re: Cousins of the Triangular Numbers Post by Icarus on Nov 25th, 2006, 5:26pm 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). |
||
|
Title: Re: Cousins of the Triangular Numbers Post by ecoist on Nov 25th, 2006, 8:24pm 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. |
||
|
Title: Re: Cousins of the Triangular Numbers Post by TenaliRaman on Nov 25th, 2006, 8:47pm on 11/25/06 at 20:24:09, ecoist wrote:
You gotta be a moderator+uberpuzzler for that uber cool power. -- AI |
||
|
Title: Re: Cousins of the Triangular Numbers Post by Sameer on Nov 25th, 2006, 10:51pm on 11/25/06 at 20:47:49, TenaliRaman wrote:
Or some seniority ;) . |
||
|
Title: Re: Cousins of the Triangular Numbers Post by TenaliRaman on Nov 25th, 2006, 11:26pm on 11/25/06 at 22:51:03, Sameer wrote:
Oh you mean this ::), . -- AI |
||
|
Title: Re: Cousins of the Triangular Numbers Post by jollytall on Nov 26th, 2006, 2:08am 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:
|
||
|
Title: Re: Cousins of the Triangular Numbers Post by Icarus on Nov 26th, 2006, 12:03pm 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 ] .... |
||
|
Title: Re: Cousins of the Triangular Numbers Post by Icarus on Nov 26th, 2006, 12:09pm on 11/25/06 at 20:24:09, ecoist wrote:
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? |
||
|
Title: Re: Cousins of the Triangular Numbers Post by ecoist on Nov 26th, 2006, 2:40pm Quote:
Yes. |
||
|
Title: Re: Cousins of the Triangular Numbers Post by Sameer on Nov 27th, 2006, 1:22pm on 11/26/06 at 12:03:53, Icarus wrote:
yes, that is what you learn by staying long here too!! :) |
||
|
Title: Re: Cousins of the Triangular Numbers Post by Icarus on Nov 27th, 2006, 5:32pm 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. |
||
|
Title: Re: Cousins of the Triangular Numbers Post by TenaliRaman on Nov 27th, 2006, 10:07pm 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 |
||
|
Title: Re: Cousins of the Triangular Numbers Post by Eigenray on Nov 28th, 2006, 1:14am 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. |
||
|
Title: Re: Cousins of the Triangular Numbers Post by ecoist on Nov 28th, 2006, 2:40pm Quote:
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. |
||
|
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |