I am currently doing a unit on combinatorics (the mathematical study of counting) with my precalculus students, and I was inspired to post a few counting-themed challenge problems for your enjoyment. (Also, it’s my spring break!)
As you probably know, a chess board consists of 64 squares arranged in eight rows and eight columns.
- How many squares—of any size—are on a chess board? Each of the 64 smallest squares count, of course, but there are also larger ones; for example, the four squares in the upper left corner form a 2×2 square.
- How many squares of any size would there be on a 9 by 9 chess board? 10 by 10? n by n?
- How many rectangles of any size and shape are there on a chess board? Is this easier or harder than counting squares?
- How about rectangles on 9 by 9, 10 by 10, n by n, or m by n chess board?
I think that on an n by n chessboard, there would be n^2+(n-1)^2+ (n-2)^2… until it gets down to 0. So on an 8 by 8 board there would be 204 squares. I’m not sure about the rectangles though…
Squares:
1 nxn square
2×2 (n-1)x(n-1) squares
…
jXj (n-j+1)X(n-j+1) squares
total = sum_{j=1}^n j^2 = n(n+1)(2n+1)/6 squares
Rectangles:
How many jxk rectangles are there?
Put one in the top left corner, then slide it over until it hits the top right. That makes (n+1-k) along the top row.
Sliding down, there are (n+1-j) down the side.
The total number of rectangles is
sum_{j,k=1}^n (n+1-k)(n+1-j)
first fix j and sum over k. you get
sum_{j=1}^n (n+1-k)n(n+1)/2
This is just a constant times the same sum you just did, so it comes to.
n^2(n+1)^2/4.
Another way to think of it is that any given rectangle can be specified by four numbers, x1, x2, y1, y2. x1 gives the starting row, x2 the ending row, y1 the starting column, y2 the ending column. Require
0<=x1<x2<=n. For a given choice of x1, there are (n-x1) choices available for x2. Summing over the possible values of x1 gives n(n+1)/2 possible pairs (x1,x2). Each x pair can go with any y pair, so square the number to get total rectangles.
Generalization to mxn is
n(n+1)/2*m(m+1)/2 rectangles
This is old. Let’s try something harder.
How many squares are there on the chessboard (or the generalized chessboard), if the only condition is that all four vertices of the square are on the crosshairs of the board (9×9 for a chessboard)? So, the sides of a square don’t have to be parallel to the sides of the chessboard.
Counting rectangles is much harder, I don’t believe there is a closed formula for that. 😉
Current CUNY math challenge asks how many non-square rectangles are on a chessboard. Nice little twist for their opening problem.
I mention it here.
Someone is tracking the contest, with all problems, here.
I know that this is off topic but I am host of a mathematics podcast
Combinations
and Permutations that I think that your readership may find
interesting. On the last episode we have covered the four color theorem and some new ideas for mathematical journals. You can find the podcast on iTunes or through our host. Give us a listen, you
will not be disappointed
Veky
On the nxn crosshair array (n=9 for chessboard), the number of jxj “upright” (not rotated) squares is (n-j+1)^2 as mentioned above.
Each of these jxj upright squares contains (j-2) inscribed oblique squares (touching it on all four sides), so we have to count (j-1) for each jxj square (to include the jxj square itself).
Summing (j-1)(n-j+1)^2 over 2<=j<=n gives (n^4 – n^2)/12 and this is 540 for n=9.
Pingback: Chessboard counting: solutions and further challenges « The Math Less Traveled
Pingback: Steps that Multiply - “Math Teachers at Play” Blog Carnival #4
i read the answer to this prblem and i do not understand why you divide by 6 on the closed formula for the squares calculation.
I would appreciate a reply ASAP
thank you!!!
Carolina:
I’m not sure there is an explanation that specifically explains why a factor of 1/6 shows up in the closed form for a sum of squares. To understand where the 1/6 comes from just requires understanding how to derive a closed form for a sum of squares. Wikipedia has some explanations (although that page badly needs some editing in places…)