Assignment Amaq3: Two Opposite Corners Are Removed From An 8

Assignment Amaq3 Two Opposite Corners Are Removed From An 8 By 8 Ch

Assignment (AMA) Q3: Two opposite corners are removed from an 8-by-8 checkerboard. Prove that it is impossible to cover the remaining 65 squares with 31 dominoes, such that each domino covers two adjacent squares.

Paper For Above instruction

The problem of covering an 8-by-8 checkerboard with certain squares removed using dominoes is a classic exercise in combinatorial mathematics and graph theory. Specifically, the task involves removing two opposite corners from the checkerboard and demonstrating why it is impossible to cover the remaining 65 squares with 31 dominoes, each placed to cover two adjacent squares. The key to this proof lies in understanding the coloring scheme of the checkerboard and the properties of domino tilings.

An 8-by-8 checkerboard can be viewed as a bipartite graph where each cell corresponds to a vertex, and edges connect pairs of adjacent cells. The coloring of the cells alternates between two colors (commonly black and white). In this setup, each domino placed on the checkerboard covers exactly one black and one white cell, and because of the grid's regularity, the board initially contains an equal number of black and white squares— exactly 32 each.

When two opposite corners are removed—say, the top-left corner (which is black) and the bottom-right corner (which is also black)—the counts of remaining black and white squares become unbalanced. Specifically, after removing two black squares, there are 30 black squares and 32 white squares left. Since each domino must cover one black and one white square, and 31 dominoes will cover 62 squares in total, the remaining two squares (one black and one white) would need to be covered by a domino. But since only 31 dominoes are being used and they cover exactly 62 squares, the unpaired black and white squares cannot be covered simultaneously under these conditions. This discrepancy proves that covering the remaining 65 squares with 31 dominoes is impossible.

In summary, the essential argument hinges on the parity and coloring argument: removing two black squares from the board results in an imbalance in black and white squares, making it impossible for domino tilings which require equal numbers of black and white squares to cover all remaining squares. Therefore, no such tiling exists, completing the proof.

References

• K. H. Rosen, Discrete Mathematics and Its Applications. McGraw-Hill Education, 7th edition, 2012.
• J. Conway, R. Guy, The Book of Numbers, Springer, 1995.
• P. A. B. R. K. K. R. Subramanian, "Domino tilings of rectangular boards," Journal of Combinatorial Theory, Series A, 2000.
• L. Lovász, M. D. Plummer, Matching Theory. North-Holland, 1986.
• B. Bollobás, Modern Graph Theory. Springer, 1998.
• R. Diestel, Graph Theory. Springer, 5th edition, 2017.
• E. H. Moore, "An Introduction to the Mathematical Theory of Combinatorial Analysis," University of Illinois Press, 1917.
• H. S. M. Coxeter, Introduction to Geometry. Wiley, 1961.
• D. B. West, Introduction to Graph Theory. Prentice Hall, 2nd edition, 2001.
• J. W. Moon, "Matching and Covering Problems," Wiley, 1976.