Recitation 1

Exercise: Domino Tiling: Consider an 8×8 chessboard, and remove two squares at opposite corners. Given (large) dominoes that cover 2 adjacent squares, is it possible to cover all of the remaining squares on the chessboard without overlapping dominoes?

The idea is to color the chessboard in the usual way and observe that no matter how you place a domino it always covers one white square and one black square. As we’ve removed two squares at opposite corners and they are of the same color, the numbers of white squares and black squares are not balanced. Hence it is impossible to cover the remaining squares without overlapping dominoes.

You can think about a more general question. Consider an m x n chessboard with two squares at opposite corners, what are the values of m and n when it is possible to cover the chessboard without overlapping dominoes?

Exercise: Quarter Covering: Suppose we have a rectangle and 25 quarters (the coin), and that we can cover the rectangle entirely by the 25 quarters in some manner. Here the quarters could possibly overlap. Now, suppose further that a dime has half the diameter of a quarter, so it has one fourth the area. Is it possible to cover the same rectangle completely using 100 dimes?

Split the rectangle into four congruent sub-rectangles (by connecting opposite midpoints): each can then be covered by 25 dimes following whichever pattern of quarters covered the original.

It is also true if we replace the rectangle by a triangle in the original question. How do you use the same technique to prove this?

Leave a Reply

Your email address will not be published. Required fields are marked *