http://www.research.att.com/~njas/sequences/A002717
2009/10/22 Josh Metzler <[email protected]> > > On Sunday 18 October 2009 11:34:59 pm 2shar007 wrote: > > In the puzzle, /_\ > > /_\/_\ > > /_\/_\/_\ this is having 10 > > vertices, we are to find the no.of triangles which is 13 here > > This was a fun puzzle. I am only going to consider complete triangles > (that > is, 1, 3, 6, 10, etc. vertices), and I am going to derive an answer based > on > the number of rows (so, 0 rows for 1 vertex, 1 row for 3, 2 rows for 6, > etc). > > First, it is easy to see that adding row n adds n + (n-1) + (n-2) + ... + 1 > = > n*(n+1)/2 triangles pointing up. > > Drawing out a few more rows we can see that the number of new triangles > pointing down is equal to (n-1) + (n-3) + (n-5) + ... > > If n is odd, then we can say n = 2k+1, so this is 2k + 2k-2 + 2k-4 + ... > which > is 2*(k + k-1 + k-2 + ...) => 2*k*(k+1)/2 = k*(k+1). Since k = (n-1)/2, > this > is (n-1)*(n+1)/4, or (n^2-1)/4. > > If n is even we can say n = 2k, so this is 2k-1 + 2k-3 + ... It is clear > that > there are k terms here, so we will add k to each of them and subtract k at > the > end, getting 2k + 2k-2 + ... - k or k*(k+1) - k, or k^2. since k = n/2, > this > is (n^2)/4. > > So, the total number of triangles we add when we add the nth row depends on > whether n is even or odd. For odd n we have > > n*(n+1)/2 + (n^2 - 1)/4 or (3*n^2 + 2*n - 1)/4 > > For even n we have > > n*(n+1)/2 + (n^2)/4 or (3*n^2 + 2*n)/4. > > These only differ by 1/4, so to get a closed form solution we will sum > (3*n^2 + > 2*n) from 1 to x, then subtract 1/4*the number of odd rows. > > We know the sum of n^2 from 1 to x is x*(x+1)*(2*x+1)/6, and the sum of n > from 1 to x is x*(x+1)/2, so we have: > > ( 3*x*(x+1)*(2*x+1)/6 + 2*x*(x+1)/2 ) / 4 > = (2*x^3 + 5*x^2 + 3*x) / 8 > > Now we need to subtract 1/4 times the number of odd numbers from 1 to (and > including) x, which is floor((x+1)/2) > > So, put it all together, and assuming integer division, we have > > ( (2*x^3 + 5*x^2 + 3*x)/2 - (x+1)/2 ) /4 > > I've verified it for up to 5 rows: > > 0: 0 > 1: 1 > 2: 5 > 3: 13 > 4: 27 > 5: 48 > > Josh Metzler > jdmetz > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~----------~----~----~----~------~----~------~--~---
