Inspired by AOTM: Day 1
So we went to a lecture yesterday and Sir Bill Chen, a very accomplished quantitative analyst, gave a speech on his life and how mathematics has affected him. During his speech, he talked about one problem in particular which caught my mind.
"An 8x8 chessboard has two of its opposite corners removed. For example, A1 and H8. Can this board be tiled completely by a sufficient number of 2x1 rectangles with no overlap?"
The answer turned out to be no. So I decided to give the problem some actual thought and I came up with an over complicated proof using modular arithmetic.
This inspired me to make a new problem:
How many ways can you remove two tiles from an 8x8 chess board such that the board cannot be completely tiled by 31, 2x1 rectangles without overlap?
The answer is 992.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
This can be solved by way of Gomory's Theorem . Only if two squares of opposite colors are chosen will a 31-domino tiling exists. Since we can choose two white or two black squares in ( 2 3 2 ) = 4 9 6 ways each, there will be 2 × 4 9 6 = 9 9 2 "mutilated chessboards" that cannot be tiled by 3 1 dominos.
(A proof of Gomory's Theorem is given under the Theorem 1.1 on pages 12-14 here .)