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 -~----------~----~----~----~------~----~------~--~---
