2
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.