2
$\begingroup$

i cam across this puzzle, we are supposed to find out the total number of squares present in this picture...

enter image description here

as being a computer programmer i designed a algo in my head for the solution and did a dry run in my head as well.

Start counting by square with highest dimension and then decrement the dimension by 1 step by step and at every decrement iterate the whole graph for matching dimensions & count them untill the dimension becomes zero... so

enter image description here

4x4 squares = 1 3x3 square  = 4 2x2 squares = 9 1x1 squares = 16 

that makes 30 squares..

i was thinking isn't there a mathematical formula to calculate the number of sub-squares in a given squared-section of graph?

p.s.

i can see a pattern, here in the above square(4) + square(3) + square(2) + square(1) but i don't enough skills in discrete mathematics & numerical analysis to bring it down to an equation or formula but i am sure the formula already exists

  • 0
    in the comments there you can find the formula2012-11-27

1 Answers 1

3

It is $\sum_{k=1}^{n} k^2 = \frac{1}{6}n(n+1)(2n+1)$

which can be prooved via induction.

For $n=4$ this will give you $\frac{1}{6}\cdot4\cdot5\cdot9=30$

  • 0
    the second part.. i want to know the steps used to arrive at this conclusion... for the learning purposes..2012-12-02