Last week us looked at methods to count paths along the edges of a rectangular grid. Currently we’ll look in ~ a companion problem: counting the number of squares (or rectangles) of every sizes in a square (or rectangular) grid. This, too, is a an extremely common question, and I’ll be picking just a few of many answers we’ve offered to variants the the problem.
You are watching: How many spaces on a checker board
Squares in an 8×8 or n×n board
We’ll begin with a question from the very first week Ask Dr. Math was in operation, in November 1994:
Chessboard SquaresDear Dr. Math,We room students native Sherwood elementary in Edmonds, WA. We have actually been working on troubles in which we investigate patterns and functions. We operated on a problem called the chessboard squares. We uncovered that there are 204 squares ~ above the board and also we uncovered several methods to look in ~ it. We discovered that girlfriend would include the different squares - 1 + 4 + 9 + 16 + 25 + 36 + 49 + 64. We did this and it worked since of the pattern, however our teacher wants to understand why that works and also if there is a quick method to gain to the answer. What if there was a 100 by 100 board? Is there a method to usage a function to find this out?We would love to hear indigenous you.6th grade student in Mrs. Moore"s room.To clarification the question, here are all the (1+4+9=14) squares in a 3×3 grid:
Doctor Ken answered:
Hello there!I think I determined what you mean, and I think it"s a fantastic question! You median the number of squares of any kind of size, right? so in the over sum, the 1 coincides to the number of 8x8 squares, the 4 is the number of 7x7 squares, and so on, right? let us recognize if it"s not.I won’t try to present all 204, however for example here space the 4 7×7 squares:
Here"s a clue around why it works. Photo the chessboard tacked up on a wall. Then let"s say you have actually a 5x5 square sitting in the lower left corner. Where else can you slide that square to? Well, you can keep it there, or you can slide it one space to the right, or 2 spaces to the right, or 3 spaces come the right; or you can slide it up zero, up one, up two, or up 3 spaces. Also, you might do both, and slide it up one and over two, or any of the various combinations of slidings.Here room the 16 means you could slide it (including leaving it alone!):
They exchange mail to the 16 locations the top right corner could be located.
So there room four choices for sliding in each of the 2 directions, right? Zero spaces, one spaces, two spaces, or three. For this reason the number of different places you might put the 5 by 5 square is 4 times 4 (4 in every of the 2 directions).How many different places can you placed a 4 by 4 square top top the board? deserve to you come up v a formula, so that if ns tell you the dimension of the square (like five by five, or four by four), you can tell me the variety of different areas you could put it in the chessboard?What we find is that for a k×k square in an n×n board, there are ((n-k+1)) possible positions in every direction, for a full of ((n-k+1)^2) such squares. For the total, we just have actually to add these together. This can be created as $$sum_k=1^n (n-k+1)^2 = n^2+(n-1)^2+cdots+1^2$$ but since the numbers gift squared selection from (n) under to 1, this can more 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 inquiry is also really interesting. I"m very impressed that you"re doing that in elementary school school; i didn"t check out that trouble until high school!You desire to know a formula because that the sum of the first n perfect squares. Well, it"s type of tricky to derive, yet I do take place to recognize what the is. Ordinarily, ns wouldn"t just offer it come you without some kind of evidence or derivation, or at least some note of what"s in reality going on, but the only proof I know 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 concept 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 out to make sure that it works. If you have any an ext questions, send castle on in!We have disputed this formula numerous other times; following week I’ll present several proofs, and ways come discover this formula (which math induction doesn’t execute for us). We’ll start, in fact, through a solution to a question about this very answer, which was later on attached to the same page.
Counting squares again …
Next, we have actually a 1997 question, even much more specifically questioning for a an easy formula:
Checkerboard SquaresMy teacher provides us a problem of the week and also I haven"t yes, really been maybe to number out this last one. Here"s the question:Say you have actually an 8x8 checkerboard. Over there are numerous other little and big squares inside of the so counting them all how plenty of are there? (e.g. Counting every the 1x1,2x2,3x3,4x4,5x5,6x6,7x7,8x8). Mean you have actually a square checkerboard of some various other size - not 8x8 - what is the easiest method to find how plenty of squares there room in it?Make certain that once you room done you will have the ability to find the number of squares in any type of size checkerboard within 2 minutes.I do the efforts counting the squares individually, yet that wouldn"t be quick enough for 12x12. Might you please give me some tips for exactly how to strategy this problem?Thanks,TashDoctor Anthony answered, beginning this time v the the smallest square:
Consider the left hand upright edge that a square of size 1 x 1. This edge deserve to be in any one that 8 positions. Similarly, the optimal edge can occupy any type of one the 8 positions because that a 1 x 1 square. Therefore the total variety 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 peak edge 7 positions, providing 7 x 7 = 49 squares of size 2 x 2.Continuing in this way we gain squares of size 3 x 3, 4 x 4 and also so on. We deserve 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 --------------- total = 204(This, there is no a closed-form formula, would certainly be an excellent enough to give solution for a 12×12 plank within 2 minutes; but the formula will certainly be simpler for really huge boards!)
Then he gave the formula, again with no proof:
There is a formula because that the amount of squares that the integers 1^2 + 2^2 + 3^2 + ... + n^2 n(n+1)(2n+1) amount = ------------ 6In our case, through n = 8, this formula provides 8 x 9 x 17/6 = 204.Again, we’ll obtain to the proof next week.
… and also counting rectangles
But then he suggested a different problem, one the leads an extremely easily come a formula:
As an extension to this problem, you might want to calculate the number of rectangles that can be drawn on a chessboard.There space 9 vertical lines and 9 horizontal lines. To type a rectangle you should choose 2 the the 9 vertical lines, and also 2 of the 9 horizontal lines. Each of these have the right to be done in 9C2 ways = 36 ways. Therefore the number of rectangles is given by 36^2 = 1296.Here is an example: In our 8×8 chessboard, brand the upright lines 1 with 9, and similarly the horizontal lines. Any selection of two pairs, such as (2, 5) and also (3, 7) here, defines a rectangle:
There space (9choose 2=frac9cdot82cdot1 = 36) ways to select each pair, because that a total of (36cdot 36=1296) possible rectangles. (This is, of course, far much more than the number of squares, i m sorry is a subset of the rectangles.)
The same can be excellent to count rectangles in a general 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$$ because that example, in a 2×3 rectangle, there space (frac2cdot 3(2+1)(3+1)4 = 18) rectangles (remember that a square is a sort of rectangle):
Squares in one m×n rectangle: acquiring started
Now let’s relocate on to a harder problem: What if the whole grid is a rectangle rather than a square, but we’re tho counting squares? below is a concern from 2003:
Formula because that Squares inside RectanglesIs over there an equation for how numerous squares there are in a rectangle separated up into 1cm blocks? This is choose the common chessboard puzzle.Doctor Jaffee answered, giving a hint fairly than a full answer:
Hi Jamie,There is a formula that will calculate the variety of squares in a rectangle. Right here is exactly how I discovered it.First, let"s consider only rectangles whose broad is 1. A 1x1 rectangle contains exactly one square, a 1x2 rectangle has two squares, a 1x3 rectangle includes three squares, etc. In general, if the size of a rectangle space 1xn, there will be n squares.That to be easy, and also I most likely haven"t told girlfriend anything friend didn"t currently know.This is trivial; below are the 5 squares in a 1×5 rectangle:
But beginning with straightforward case is a classic approach to problem solving, and also we can build on this:
Now let"s consider rectangles whose width is 2, starting with a 2x2 rectangle. We skip the 2x1 rectangle since we"ve already considered that in the ahead case. A 2x2 rectangle is composed of 4 squares whose dimensions are 1x1 and one square whose dimensions space 2 x 2. This provides us a total of 5 squares. I"m going to produce a table in which ns list the width, length, variety of 1x1 squares, variety of 2x2 squares, and total number of squares. W x together 1x1 2x2 complete ----- --- --- ----- 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 the if you have 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 recognized an noticeable pattern: The total increases through 3 when the length increases by 1. Deserve to you check out a factor to believe this is always true? Hint: Here, in red, space the 3 squares that are added when we prolong from 2×4 come 2×5:
I repetitive this process for 3xn rectangles, 4xn rectangles, 5xn rectangles, till I recognized that there to be a pattern developing. If the width is m and also the length is n, I was able to write the total variety of squares in regards to m and n.Give it a shot and if you desire to check your answer with me or if girlfriend have obstacles or various other questions, write earlier to me and also I"ll try to assist you some more.Take some time to play through this prior to reading on.
Squares in an m×n rectangle: a formula
Jamie created again the following day; as it was not a reply, it was treated as a brand-new question (and the two were never ever connected!):
Squares in Rectangle FormulaWhat is the equation because that the variety of squares in a rectangle (like the chessboard puzzle)? ns have settled that if the broad is 2, climate the formula for 2xn is same to 3n-1. Is over there an equation because that a rectangle v a width of three? If so, exactly how do you work-related it out and what is it?I have 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 basically what physician Jaffee had actually done; Jamie has just made the next table. (Do you see an error in the table? That may be why Jamie didn’t see a pattern!)
Doctor Anthony answer this time, and also (as he frequently did) went every the method to a formula:
In the general case we have actually an n x m rectangle-shaped board.Consider the left-hand vertical edge the a square of dimension 1 x 1. This edge can be in any type of one of n positions. An in similar way the peak edge deserve to occupy any one of m positions because that a 1 x 1 square. For this reason the total number of 1 x 1 squares = n x m.Again, this is the evident case; however it beginning a process. We’ll be counting the number of locations because that a square the a provided size, quite than boosting the size of the board step by step:
For a 2 x 2 square the left-hand edge deserve to occupy (n-1) positions and also the height edge (m-1) positions, providing (n-1)(m-1) squares of dimension 2 x 2.Continuing in this means we acquire squares of dimension 3 x 3, 4 x 4 and also so on.If we have actually an 8 x 9 plank the numbers of squares room 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 concern is, have the right to we revolve this sum into a straightforward formula?
We’ll assume that (m>n), and also let t it is in the difference in between the two; climate we can write the summation and use algebra to leveling the result:
For the general case of one n x m board, whereby m = n + t n nWe need SUM
As a check, us can try the formula top top the example we included up manually above:
In the example over t = 1 and so No. The squares = 8 x 9/6<16 + 3 + 1> = (72/6)<20> = 240 (as required)This gives us factor to trust the formula.
The basic formula because that an (n x n+t) board is that given in (1) above. No. Of squares =
We can likewise rewrite this in regards to our original (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 plenty of squares space there in 20 x 30 rectangle-shaped board?Here n = 20 and 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 space there in a 31 x 42 rectangular board?Here n = 31 and also t = 11 variety of squares = 31 x 32 x (1/6) x <62 + 33 + 1> = (1/6) x 31 x 32 x 96 = 15872He closed with a testimonial of the facts essential for the derivation:
For the moment I think you should just remember the formula number of squares = (1/6)*n(n + 1)(2n + 3t + 1)where the rectangle has actually sides n and also n + t.The derivation relies on understanding the formulae because that the sums of series 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 more than likely be covering this subject in lessons before long and also the formula I provided for the number of squares in a rectangle will then end up being clear.If you desire to watch the source of the sums of the series above you deserve to write in again, yet at the minute you may discover the work an overwhelming to follow.
Doing that again, more visuallyIn 2004 a reader, Brooke, asked because that a fuller explanation:
I quiet don"t obtain how you came to 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 recognize where you have obtained the 6 from and also how to ar the equation right into brackets. Is there some method that friend can suggest me in the ideal direction to coming to this conclusions?Doctor Greenie obtained the formula using technique that parallels physician Anthony’s yet is less algebraic:
Hi, Brooke -I uncovered Doctor Anthony"s explanation of the problem on that web page quite good -- yet then, I currently understand the problem. Ns think there are a couple of points that can be done to boost his presentation that the product on the page.The vital to his an approach of deriving the formula (which is the method I uncover easiest come understand) is to consider the rectangle as a square selection of squares with "extra" columns of squares included on.Here is just how he would think that a 3×5 rectangle:
With this approach, we can find(1) The variety of squares in an n-by-n square is 1^2 + 2^2 + 3^2 + ... + n^2This sum is provided by the formula n(n + 1)(2n + 1)/6Again, we’ll be looking in ~ derivations the this formula next week.
(2) as soon as we start with this n-by-n square and add 1-by-n columns the squares, the number of additional squares in the overall range resulting from the addition of each brand-new column is 1 + 2 + 3 + ... + nThis amount is provided by the formula n(n + 1)/2For example, adding the fourth column come our square to add these six squares:
Adding the fifth column adds one more six:
So each column adds this same number of squares (which, you may notice, is the nth triangle number).
So, for example, the total variety of squares in a 10-by-6 selection of squares is the number of squares in the square 6-by-6 array, plus 4 (that is, 10-6) times the number of squares added with each additional column that 6 squares. Physician Anthony uses "n" together the measurement of the square array of squares and "t" together the number of additional columns, so the total number of squares in this instance is given by the formula n(n + 1)(2n + 1)/6 + (t)*
See more: What Do You Call Each 1 Or 0 Used In The Representation Of Computer Data?
The algebra that followed deserves to be slowed under a bit:
Perhaps the many confusing part of medical professional Anthony"s response (in my mind, in ~ least) is that he disguises the formula over by combining the 2 terms right into a single fraction v a usual denominator. To execute that, the second portion is multiply by 3 in the numerator and also denominator (to gain the usual denominator "6"), the 2 fractions are merged into a solitary fraction, and also the typical factors "n" and also "(n+1)" in the numerator are factored out. The actions are: n(n+1)(2n+1) (t)(n)(n+1) ------------ + ----------- 6 2 n(n+1)(2n+1) 3(t)(n)(n+1) ------------ + ------------ 6 6 n(n+1)(2n+1) + 3(t)(n)(n+1) --------------------------- 6