Chessboard counting

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.

  1. 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.
  2. How many squares of any size would there be on a 9 by 9 chess board? 10 by 10? n by n?
  3. How many rectangles of any size and shape are there on a chess board? Is this easier or harder than counting squares?
  4. How about rectangles on 9 by 9, 10 by 10, n by n, or m by n chess board?
About these ads
This entry was posted in challenges, counting and tagged , , , , . Bookmark the permalink.

10 Responses to Chessboard counting

  1. JM says:

    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…

  2. meichenl says:

    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

  3. Veky says:

    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. ;-)

  4. Jonathan says:

    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.

  5. 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

  6. Geek says:

    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.

  7. Pingback: Chessboard counting: solutions and further challenges « The Math Less Traveled

  8. Pingback: Steps that Multiply - “Math Teachers at Play” Blog Carnival #4

  9. Carolina says:

    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!!!

  10. Brent says:

    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…)

Comments are closed.