The props for this problem are a chessboard and 32 dominoes. Each domino is of such size that it exactly covers two adjacent squares on the board. The 32 dominoes therefore can cover all 64 of the chess-board squares. But now suppose we cut off two squares at diagonally opposite corners of the board and discard one of the dominoes, as shown in Figure 1.3. Is it possible to place the 31 dominoes on the board so that all the remaining squares are covered? If so, show how it can be done. If not, prove it impossible.
Answer:
It is impossible to cover the mutilated chessboard (with two opposite corner squares cut off) with 31 dominoes, and the proof is easy. The two diagonally opposite corners are of the same color. Therefore their removal leaves a board with two more squares of one color than of the other. Each domino covers two squares of opposite color, since only opposite colors are adjacent. After you have covered 60 squares with 30 dominoes, you are left with two uncovered squares of the same color. These two cannot be adjacent, therefore they cannot be covered by the last domino. An interesting question now arises. Suppose that any two squares of opposite color are removed from a chessboard, say squares A and B in Figure 1.14. Can the remaining 62 squares always be completely covered by 31 dominoes? The answer is yes, and Ralph Gomory hit upon a simple, elegant proof. Removing any two squares of opposite color divides the closed path (one square wide) into two segments. Each segment must contain an even number of squares that alternate colors. Obviously each segment can be covered with n dominoes, where n is half the number of squares in the segment. Think of the dominoes as little boxcars that can be placed end to end along each of the two segments. Hence the task is always solvable.
Answer:
It is impossible to cover the mutilated chessboard (with two opposite corner squares cut off) with 31 dominoes, and the proof is easy. The two diagonally opposite corners are of the same color. Therefore their removal leaves a board with two more squares of one color than of the other. Each domino covers two squares of opposite color, since only opposite colors are adjacent. After you have covered 60 squares with 30 dominoes, you are left with two uncovered squares of the same color. These two cannot be adjacent, therefore they cannot be covered by the last domino. An interesting question now arises. Suppose that any two squares of opposite color are removed from a chessboard, say squares A and B in Figure 1.14. Can the remaining 62 squares always be completely covered by 31 dominoes? The answer is yes, and Ralph Gomory hit upon a simple, elegant proof. Removing any two squares of opposite color divides the closed path (one square wide) into two segments. Each segment must contain an even number of squares that alternate colors. Obviously each segment can be covered with n dominoes, where n is half the number of squares in the segment. Think of the dominoes as little boxcars that can be placed end to end along each of the two segments. Hence the task is always solvable.
No comments:
Post a Comment