# Professor Halfbrain's chessboard dissection theorem

Professor Halfbrain has spent another weekend on analyzing and dissecting chessboards. His efforts resulted in the following surpring theorem.

Professor Halfbrain's chessboard dissection theorem:
For every $m\ge1.000.000$ and $n\ge1.000.000$, the $m\times n$ chessboard can be dissected into pieces of size $~4\times6$, $~6\times4$, $~5\times7$, $~$and $~7\times5$.

Is this theorem true, or has the professor once again made one of his mathematical blunders?

The theorem is

true

First note that any number >= 11 can be written as a sum of 4,6 and 5 but also as a sum of 4,6 and 7:

11 = 6 + 5 = 4 + 7
12 = 6 + 6
13 = 4 + 4 + 5 = 6 + 7
14 = 5 + 5 + 4 = 7 + 7
For higher numbers just add 4 to these.

Knowing this, fill the top row with blocks having a width of 4,6 or 5. Now we want to level the bottom of these blocks by adding same-width blocks underneath it. The smallest value of this is the least common factor of the heights of these blocks. LCM(6,4,7) = 84. In other words:

As long as the width of the board >= 11 and the height > 84 you can always remove 84 rows.

Now do this: Keep removing 84 rows until the total height is divisible by 5. This can maximally take 4 steps.

Now do something similar for the columns:

Fill the left column with blocks having a height of 4,6 or 7. Now we want to level the right side of these blocks by adding same-height blocks to the right of it. The smallest value of this is the least common factor of the widths of these blocks. LCM(6,4,5) = 60. In other words:

As long as the height of the board >= 11 and the width > 60 you can always remove 60 columns.

Now do this: Keep removing 60 rows until the total width is divisible by 7. This can maximally take 6 steps.

Using this algorithm you'll end up with a board with the width divisible by 7 and the height divisible by 5 so we can fill this board with 7x5 blocks, proving the theorem.