Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How many squares of all sizes arise using an $n$-by-$n$ checkerboard? How many triangles of all sizes arise using a triangular grid with sides of length $n$ ?

share|improve this question
1  
What have you tried? –  Ross Millikan Jun 27 '11 at 19:36
    
I actually think I have the first part down, it should just be $\displaystyle \sum_{i=1}^{n}i^2$. For the second part, I've got nothing. –  rapidash Jun 27 '11 at 19:40
1  
the square formed by a2,b1,b2,b3,c2 (in chess notation) is not counted? You need to clarify which squares you intend to count... –  Aryabhata Jun 27 '11 at 19:44
    
@Aryabhata: just curious...How does chess notation work? (I suppose I could try googling "chess" or the like). –  amWhy Jun 27 '11 at 19:51
    
@amWhy: The columns are labelled a to h (starting from left) and rows are 1 to 8 starting from bottom. a1 is the bottom left square. –  Aryabhata Jun 27 '11 at 19:56

3 Answers 3

up vote 2 down vote accepted

HINT:

It is very simple to see how many 1-squares fit. What about a 2-square (natural notation)? Well, let's only place the top-left square. How many places can we put the top-left square of a 2 by 2 on the board and have it fit? And so on? This leads to your intuition being correct.

This works for triangles too - but I'll let you figure that out.

share|improve this answer
    
It is slightly harder for triangles when you try to count those pointing in the other direction. –  Henry Jun 28 '11 at 0:02

For the triangular grid, can you convince yourself that all the triangles are equilateral (assuming the grid is)?

share|improve this answer

Your answer for the squares is correct. For the triangles, you do something similar, with a twist.

For the triangles in the original direction you have 1 big triangle, 3 triangles one size smaller, 6 another size smaller and you should be able to persuade yourself that these continue as the triangle numbers $1,3,6,10,15,21,\ldots$.

For the triangles in the other direction, if you have an original triangle with an even length side you have 1 triangle with side half that of the original triangle, 6 triangles one size smaller, 15 another size smaller etc., while if you have an original triangle with an odd length side you have 3 triangles with side half that of the original triangle rounded down, 10 triangles one size smaller, 21 another size smaller etc.

Adding all these up is not trivial, but you should get OEIS A002717 as your result.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.