2
$\begingroup$

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$ ?

  • 0
    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.2011-06-27
  • 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...2011-06-27
  • 0
    @Aryabhata: just curious...How does chess notation work? (I suppose I could try googling "chess" or the like).2011-06-27
  • 0
    @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.2011-06-27
  • 0
    Aryabhata's question is whether you only count squares with sides parallel to the sides of the board, or count diagonally positioned squares as well.2011-06-27
  • 0
    For orthogonal squares you have it right.2011-06-27
  • 0
    @aryabhata: Thanks! I sort of figured, the column-letter/row-number...but would have guessed row 1 at top...good to know!2011-06-27
  • 0
    @amWhy: for this purpose it doesn't matter which goes at the top or right (it is just a rotation). If you are playing chess, it does, as White goes on ranks 1 and 2 to start, Black on 7 and 8.2011-06-27
  • 0
    Thanks, @Ross...I used to know this (while playing chess long ago)..but it's been awhile ;-). I realize the row numbers (top down, bottom up) wasn't important in relation to the problem at hand; I was curious with respect to the game of chess.2011-06-27

3 Answers 3

2

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.

  • 0
    It is slightly harder for triangles when you try to count those pointing in the *other* direction.2011-06-28
2

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

1

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.