Computer Science
Squares on a chessboard
How many squares of any size can you find on an 8 by 8 chessboard? Then generalise.
- Hint 1Count the 1 by 1 squares, then the 2 by 2 squares. Where can the top-left corner of a 2 by 2 square go?
- Hint 2A k by k square has its top-left corner in a (9 − k) by (9 − k) grid of positions.
- A k by k square fits in (9 − k) positions across and (9 − k) down, so there are (9 − k)² of them.
- Summing k = 1 to 8 gives 8² + 7² + … + 1².
- That is 64 + 49 + 36 + 25 + 16 + 9 + 4 + 1 = 204.
- For an n by n board: 1² + 2² + … + n² = n(n + 1)(2n + 1)/6.
Where it lands: 204; in general n(n + 1)(2n + 1)/6.
The trap: Answering 64, or adding only the 1 by 1 squares and the whole board.
What a tutor might ask next: How many rectangles are on the board?
Now do one out loud. In the interview you think aloud with a tutor. Try a Computer Science problem with hints, follow-ups and Mia's feedback on how you think.