Problem Links
Author: Pravakar Wang
Tester: Ankur Goel
Editorialist: Ankur Goel
Difficulty
Medium
Problem
Martians build their houses in triangular shapes. They have a tradition that for every new generation, new row of such triangular houses are built joining the previous generation houses as in figure ( assume that number of newly built houses exactly follows the triangular pattern). In this pattern, the people of mars develop colonies.
Chef saw an overview NASA overview photographs of such mars colonies. He was very fascinated at the manner the houses are built and he is interested in finding out the number of triangles that can be seen in such colonies for a given number of generations. Help Chef count the number of triangles in such colonies.
Note: The first figure represents a colony having one generation, the second fig represents a colony having two generations and the third one represents a colony having three generations.
Explanation
Let T(n) be the number of total triangles in the figure.
Then T(n) = (Sum of the first n triangular numbers) + (Sum of the downward triangles)
- if n is odd, then the number of downward pointing down is the sum of the first even triangular numbers (second + fourth + … + (n-1)th )
- if n is even, then the number of downward pointing triangles is the sum of the first odd triangular numbers (first, third, fifth, … + (n-1)th ).
In order to generate each of the first n-even triangular numbers (even for the n-values such as n=2, n=4, n=6, etc., for some natural number k), I substituted k=2n into the formula I knew for triangular numbers: . Beginning with T(1),…, we obtain the sequence of triangular numbers generated by even integers {3, 10, 21, 36, 55, …}.
In order to generate each of the first n-odd triangular numbers (such as n=1, n=3, n=5…) we consider the function where m=2n-1 for natural numbers, n. This will generate the sequence of the triangular numbers from odd n-values.
Author’s Solution
Author’s solution can be found here