Last week us looked at methods to count paths along the edge of a rectangular grid. Currently we’ll look in ~ a companion problem: counting the variety of squares (or rectangles) of all sizes in a square (or rectangular) grid. This, too, is a really common question, and I’ll be picking simply a couple of of countless answers we’ve offered to variants of the problem.

You are watching: How many squares on a checkerboard

## Squares in an 8×8 or n×n board

We’ll begin with a question from the very very first week Ask Dr. Math remained in operation, in November 1994:

Chessboard SquaresDear Dr. Math,We space students indigenous Sherwood elementary in Edmonds, WA. We have been functioning on problems in which we investigate patterns and functions. We functioned on a trouble called the chessboard squares. We uncovered that there are 204 squares top top the board and also we uncovered several ways to look in ~ it. We discovered that you would include the various squares - 1 + 4 + 9 + 16 + 25 + 36 + 49 + 64. We did this and it worked because of the pattern, however our teacher wants to recognize why the works and if over there is a quick means to get to the answer. What if there to be a 100 by 100 board? Is there a means to use a role to find this out?We would love come hear native you.6th grade students in Mrs. Moore"s room.To clarification the question, right here are all the (1+4+9=14) squares in a 3×3 grid: Hello there!I think I established what you mean, and I think it"s a an excellent question! You typical the number of squares of any size, right? therefore in the above sum, the 1 corresponds to the number of 8x8 squares, the 4 is the number of 7x7 squares, and so on, right? let us understand if it"s not.I won’t try to show all 204, but for example here room the 4 7×7 squares: Here"s a clue around why it works. Picture the chessboard tacked up on a wall. Then let"s say you have actually a 5x5 square sit in the lower left corner. Whereby else deserve to you slide the square to? Well, you might keep the there, or you could slide the one room to the right, or two spaces come the right, or 3 spaces to the right; or you might slide it up zero, up one, increase two, or up three spaces. Also, you could do both, and also slide it increase one and also over two, or any of the miscellaneous combinations of slidings.Here room the 16 methods you could slide the (including leaving that alone!): They exchange mail to the 16 areas the top right edge could be located.

So there space four choices for sliding in each of the two directions, right? Zero spaces, one spaces, 2 spaces, or three. Therefore the number of different areas you could put that 5 by 5 square is 4 times 4 (4 in every of the two directions).How numerous different places might you placed a 4 by 4 square on the board? can you come up v a formula, so that if i tell girlfriend the dimension of the square (like five by five, or 4 by four), you can tell me the number of different places you could put it in the chessboard?What we uncover is that for a k×k square in one n×n board, there space ((n-k+1)) possible positions in every direction, because that a total of ((n-k+1)^2) together squares. For the total, we just have actually to add these together. This could be created as \$\$sum_k=1^n (n-k+1)^2 = n^2+(n-1)^2+cdots+1^2\$\$ but due to the fact that the numbers gift squared variety from (n) under to 1, this can an ext nicely be created as \$\$sum_k=1^n k^2 = 1^2+2^2+cdots n^2\$\$

### Making a formula

The second part of your question is also very interesting. I"m an extremely impressed that you"re doing that in elementary school; i didn"t check out that difficulty until high school!You want to understand a formula because that the amount of the an initial n perfect squares. Well, it"s sort of tricky to derive, but I do occur to understand what the is. Ordinarily, i wouldn"t just offer it come you without some sort of evidence or derivation, or at least some hints of what"s actually going on, but the just proof I understand is, i think, too sophisticated for elementary college (If I"m wrong, you re welcome let us know! i don"t desire to underestimate your capabilities!). The proof supplies a principle called mathematical induction.Anyway, the formula for the sum of the very first n perfect squares is n x (n + 1) x (2n + 1) ______________________ 6Check it the end to make certain that that works. If you have any an ext questions, send them on in!We have disputed this formula numerous other times; next week I’ll display several proofs, as well as ways come discover this formula (which mathematical induction doesn’t do for us). We’ll start, in fact, through a an answer to a question around this really answer, i m sorry was later attached come the exact same page.

## Counting squares again …

Next, we have a 1997 question, even an ext specifically asking for a an easy formula:

Checkerboard SquaresMy teacher gives us a difficulty of the week and also I haven"t really been may be to figure out this last one. Here"s the question:Say you have an 8x8 checkerboard. Over there are countless other little and huge squares inside of that so count them all how countless are there? (e.g. Counting all the 1x1,2x2,3x3,4x4,5x5,6x6,7x7,8x8). Intend you have a square checkerboard the some various other size - not 8x8 - what is the easiest method to find how plenty of squares there are in it?Make certain that once you space done friend will be able to find the number of squares in any size checkerboard within 2 minutes.I make the efforts counting the squares individually, but that wouldn"t be quick sufficient for 12x12. Can you please provide me part tips for how to strategy this problem?Thanks,TashDoctor Anthony answered, starting this time with the smallest square:

Consider the left hand vertical edge of a square of dimension 1 x 1. This edge can be in any one the 8 positions. Similarly, the top edge deserve to occupy any one the 8 positions for a 1 x 1 square. Therefore the total number of 1 x 1 squares = 8 x 8 = 64.For a 2 x 2 square the left hand edge can occupy 7 positions and also the height edge 7 positions, providing 7 x 7 = 49 squares of size 2 x 2.Continuing in this method we acquire squares of dimension 3 x 3, 4 x 4 and also so on. We have the right to summarize the outcomes as follows: dimension Of square number of squares --------------- ----------------- 1 x 1 8^2 = 64 2 x 2 7^2 = 49 3 x 3 6^2 = 36 4 x 4 5^2 = 25 5 x 5 4^2 = 16 6 x 6 3^2 = 9 7 x 7 2^2 = 4 8 x 8 1^2 = 1 --------------- full = 204(This, without a closed-form formula, would be good enough to give solution for a 12×12 plank within 2 minutes; however the formula will certainly be much easier for really big boards!)

Then he offered the formula, again with no proof:

There is a formula because that the amount of squares the the integers 1^2 + 2^2 + 3^2 + ... + n^2 n(n+1)(2n+1) amount = ------------ 6In our case, through n = 8, this formula offers 8 x 9 x 17/6 = 204.Again, we’ll obtain to the proof next week.

### … and also counting rectangles

But climate he argued a various problem, one that leads an extremely easily to a formula:

As an expansion to this problem, you can want to calculate the number that rectangles that can be drawn on a chessboard.There room 9 vertical lines and 9 horizontal lines. To form a rectangle you should choose 2 the the 9 vertical lines, and also 2 the the 9 horizontal lines. Every of these can be done in 9C2 means = 36 ways. For this reason the number of rectangles is given by 36^2 = 1296.Here is one example: In our 8×8 chessboard, brand the upright lines 1 with 9, and likewise the horizontal lines. Any an option of 2 pairs, such together (2, 5) and (3, 7) here, specifies a rectangle: There room (9choose 2=frac9cdot82cdot1 = 36) means to select each pair, for a total of (36cdot 36=1296) possible rectangles. (This is, that course, far much more than the variety of squares, which is a subset of the rectangles.)

The same deserve to be done to counting rectangles in a basic m×n rectangle. The an outcome is \$\$m+1choose 2n+1choose 2 = frac(m+1)m2frac(n+1)n2 = fracmn(m+1)(n+1)4\$\$ for example, in a 2×3 rectangle, there are (frac2cdot 3(2+1)(3+1)4 = 18) rectangles (remember the a square is a kind of rectangle): ## Squares in an m×n rectangle: acquiring started

Now let’s relocate on to a more tough problem: What if the totality grid is a rectangle quite than a square, yet we’re quiet counting squares? right here is a concern from 2003:

Formula because that Squares inside RectanglesIs over there an equation for how countless squares there room in a rectangle divided up right into 1cm blocks? This is favor the common chessboard puzzle.Doctor Jaffee answered, providing a hint rather than a complete answer:

Hi Jamie,There is a formula that will calculate the variety of squares in a rectangle. Below is just how I uncovered it.First, let"s consider only rectangles whose width is 1. A 1x1 rectangle has exactly one square, a 1x2 rectangle consists of two squares, a 1x3 rectangle contains three squares, etc. In general, if the dimensions of a rectangle space 1xn, there will certainly be n squares.That to be easy, and I more than likely haven"t told friend anything girlfriend didn"t currently know.This is trivial; right here are the 5 squares in a 1×5 rectangle: But beginning with basic case is a classic technique to difficulty solving, and we can construct on this:

Now let"s take into consideration rectangles whose width is 2, starting with a 2x2 rectangle. We skip the 2x1 rectangle because we"ve currently considered the in the ahead case. A 2x2 rectangle is composed of four squares who dimensions room 1x1 and one square whose dimensions space 2 x 2. This offers us a full of 5 squares. I"m walking to produce a table in which i list the width, length, variety of 1x1 squares, number of 2x2 squares, and total variety of squares. W x l 1x1 2x2 total ----- --- --- ----- 2 x 2 4 1 5 2 x 3 6 2 8 2 x 4 8 3 11 2 x 5 10 4 14In general, you must see that if you have actually a 2xn rectangle, the total variety of squares will certainly be 3n - 1.Here room the 14 squares in a 2×5 rectangle: He has simply well-known an obvious pattern: The full increases by 3 as soon as the length boosts by 1. Have the right to you watch a factor to think this is always true? Hint: Here, in red, space the 3 squares the are included when we expand from 2×4 to 2×5: I repetitive this procedure for 3xn rectangles, 4xn rectangles, 5xn rectangles, till I well-known that there was a pattern developing. If the width is m and also the size is n, I had the ability to write the total number of squares in terms of m and also n.Give the a try and if you want to inspect your answer v me or if you have challenges or various other questions, write back to me and also I"ll shot to assist you part more.Take some time come play through this before reading on.

## Squares in an m×n rectangle: a formula

Jamie composed again the following day; together it was not a reply, it to be treated as a brand-new question (and the two were never connected!):

Squares in Rectangle FormulaWhat is the equation because that the number of squares in a rectangle (like the chessboard puzzle)? ns have worked out that if the broad is 2, then the formula because that 2xn is equal to 3n-1. Is there an equation for a rectangle v a width of three? If so, exactly how do you job-related it out and also what is it?I have actually made a chart however can watch no relationship. Dimensions 1x1 2x2 3x3 full 3x2 6 2 0 8 3x3 9 4 1 10 3x4 12 6 2 20This is essentially what physician Jaffee had actually done; Jamie has just do the following table. (Do you check out an error in the table? That may be why Jamie didn’t watch a pattern!)

Doctor Anthony answer this time, and (as he often did) went all the means to a formula:

In the general situation we have actually an n x m rectangular board.Consider the left-hand vertical edge that a square of size 1 x 1. This edge have the right to be in any type of one the n positions. Similarly the height edge deserve to occupy any one that m positions for a 1 x 1 square. So the total variety of 1 x 1 squares = n x m.Again, this is the obvious case; however it beginning a process. We’ll it is in counting the variety of locations for a square of a provided size, quite than increasing the size of the board action by step:

For a 2 x 2 square the left-hand edge have the right to occupy (n-1) positions and the top edge (m-1) positions, offering (n-1)(m-1) squares of dimension 2 x 2.Continuing in this means we obtain squares of size 3 x 3, 4 x 4 and so on.If we have an 8 x 9 plank the number of squares space as follows: dimension of Square variety of Squares -------------- ----------------- 1 x 1 8 x 9 = 72 2 x 2 7 x 8 = 56 3 x 3 6 x 7 = 42 4 x 4 5 x 6 = 30 5 x 5 4 x 5 = 20 6 x 6 3 x 4 = 12 7 x 7 2 x 3 = 6 8 x 8 1 x 2 = 2 ---------------------------------------- total = 240Now the inquiry is, can we turn this sum right into a straightforward formula?

We’ll assume the (m>n), and let t it is in the difference between the two; then we can write the summation and use algebra to leveling the result:

For the general instance of one n x m board, whereby m = n + t n nWe need SUM = SUM*<2n + 1 + 3t>No. Of squares = *<2n + 3t + 1> .......(1)We’ll be breaking this down a little more soon, since he made a couple big leaps here.

As a check, we can try the formula on the instance we added up manually above:

In the example over t = 1 and so No. That squares = 8 x 9/6<16 + 3 + 1> = (72/6)<20> = 240 (as required)This offers us factor to to trust the formula.

The basic formula for an (n x n+t) board is that provided in (1) above. No. The squares = *<2n + 3t + 1>\$\$ extnumber the squares = fracn(n+1)(2n+3t+1)6\$\$

We can also rewrite this in terms of our initial (m = n + t), which returns \$\$ extnumber of squares = fracn(n+1)(2n+3(m-n)+1)6 = fracn(n+1)(3m-n+1)6\$\$

A pair more examples:

Example(1): How countless squares room there in 20 x 30 rectangular board?Here n = 20 and also t = 10 variety of squares = 20 x 21 x (1/6) x <40 + 30 + 1> = (1/6) x 20 x 21 x 71 = 4970Example(2): How countless squares are there in a 31 x 42 rectangular board?Here n = 31 and t = 11 number of squares = 31 x 32 x (1/6) x <62 + 33 + 1> = (1/6) x 31 x 32 x 96 = 15872He closed with a evaluation of the facts needed for the derivation:

For the moment I think you should just remember the formula variety of squares = (1/6)*n(n + 1)(2n + 3t + 1)where the rectangle has sides n and n + t.The derivation counts on learning the formulae for the sums of collection like 1^2 + 2^2 + 3^2 + 4^2 + ... + n^2 = n(n+1)(2n+1)/6and 1 + 2 + 3 + 4 + ... + n = n(n+1)/2You will probably be covering this topic in lessons before long and also the formula I provided for the variety of squares in a rectangle will certainly then end up being clear.If you want to watch the derivation of the sums of the series above you have the right to write in again, however at the minute you may discover the work daunting to follow.

### Doing that again, an ext visually

I quiet don"t obtain how you involved find the rules as: Squares in Rectangles: n(n + 1)/6*<2n + 3t + 1> Squares in Squares: (n(n + 1)(2n + 1))/6I don"t understand where friend have gained the 6 from and how to section the equation right into brackets. Is there some means that girlfriend can point me in the appropriate direction to comes to this conclusions?Doctor Greenie acquired the formula using strategy that parallels doctor Anthony’s however is much less algebraic:

Hi, Brooke -I found Doctor Anthony"s explanation of the difficulty on that web page quite an excellent -- however then, I currently understand the problem. Ns think there room a pair of things that could be done to enhance his presentation of the product on that page.The vital to his an approach of deriving the formula (which is the technique I discover easiest come understand) is to consider the rectangle as a square selection of squares with "extra" columns the squares included on.Here is exactly how he would think the a 3×5 rectangle: With this approach, we can find(1) The number of squares in an n-by-n square is 1^2 + 2^2 + 3^2 + ... + n^2This amount is provided by the formula n(n + 1)(2n + 1)/6Again, we’ll it is in looking at derivations that this formula next week.

(2) as soon as we start with this n-by-n square and also add 1-by-n columns the squares, the variety of additional squares in the overall array resulting from the addition of each new column is 1 + 2 + 3 + ... + nThis sum is given by the formula n(n + 1)/2For example, including the fourth column to our square add to these six squares:  