1974 IMO Problems/Problem 4
Problem
Consider decompositions of an chessboard into non-overlapping rectangles subject to the following conditions:
(i) Each rectangle has as many white squares as black squares.
(ii) If is the number of white squares in the -th rectangle, then
Find the maximum value of for which such a decomposition is possible. For this value of determine all possible sequences
Solution
Since each rectangle has the same number of black squares as white squares, . Clearly for to so so this forces . It is possible to decompose the board into rectangles, as we will show later. But first let us find all such sequences . Now . For a rectangle to have white squares, it will have an area of so it's dimensions are either or - neither of which would fit on a board. So .
If (which could fit as a rectangle) then . Then so . So are 6 numbers among 1-7. If is the number that is not equal to any , then so . Then . Such a decomposition is possible. Take a rectangle on the top left corner, where there are squares horizontally and vertically. Then directly below use a and a rectangle to cover the 3 rows below it. It's simple from there.
Similarly, you can find the other possibilities as or or . Tilings are not hard to find.
The above solution was posted and copyrighted by WakeUp. The original thread for this problem can be found here: [1]
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
See Also
1974 IMO (Problems) • Resources | ||
Preceded by Problem 3 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 5 |
All IMO Problems and Solutions |