Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1974 IMO Problems/Problem 4"
 
Line 1: Line 1:
 
==Problem==
 
==Problem==
 +
 
Consider decompositions of an <math>8\times8</math> chessboard into <math>p</math> non-overlapping rectangles subject to the following conditions:
 
Consider decompositions of an <math>8\times8</math> chessboard into <math>p</math> non-overlapping rectangles subject to the following conditions:
  
Line 7: Line 8:
  
 
Find the maximum value of <math>p</math> for which such a decomposition is possible. For this value of <math>p,</math> determine all possible sequences <math>a_1, a_2, \cdots, a_p.</math>
 
Find the maximum value of <math>p</math> for which such a decomposition is possible. For this value of <math>p,</math> determine all possible sequences <math>a_1, a_2, \cdots, a_p.</math>
 +
  
 
==Solution==
 
==Solution==
 +
 
Since each rectangle has the same number of black squares as white squares, <math>a_1+a_2+\ldots +a_p=\frac{64}{2}=32</math>. Clearly <math>a_i\ge i</math> for <math>i=1</math> to <math>i=p</math> so <math>32=a_1+a_2+\ldots + a_p\ge 1+2+\ldots +p=\frac{p(p+1)}{2}</math> so this forces <math>p\le 7</math>. It is possible to decompose the board into <math>7</math> rectangles, as we will show later. But first let us find all such sequences <math>a_i</math>.
 
Since each rectangle has the same number of black squares as white squares, <math>a_1+a_2+\ldots +a_p=\frac{64}{2}=32</math>. Clearly <math>a_i\ge i</math> for <math>i=1</math> to <math>i=p</math> so <math>32=a_1+a_2+\ldots + a_p\ge 1+2+\ldots +p=\frac{p(p+1)}{2}</math> so this forces <math>p\le 7</math>. It is possible to decompose the board into <math>7</math> rectangles, as we will show later. But first let us find all such sequences <math>a_i</math>.
 
Now <math>32-a_7=a_1+a_2+\ldots +a_6\ge 1+2+\ldots +6=21\implies 11\le a_7</math>. For a rectangle to have <math>11</math> white squares, it will have an area of <math>22</math> so it's dimensions are either <math>1\times 22</math> or <math>2\times 11</math> - neither of which would fit on a <math>8\times 8</math> board. So <math>a_7\not= 11\implies a_7\le 10</math>.
 
Now <math>32-a_7=a_1+a_2+\ldots +a_6\ge 1+2+\ldots +6=21\implies 11\le a_7</math>. For a rectangle to have <math>11</math> white squares, it will have an area of <math>22</math> so it's dimensions are either <math>1\times 22</math> or <math>2\times 11</math> - neither of which would fit on a <math>8\times 8</math> board. So <math>a_7\not= 11\implies a_7\le 10</math>.
Line 16: Line 19:
 
Similarly, you can find the other possibilities as <math>\{a_1,a_2,\ldots ,a_7\}=\{1,2,3,4,5,8,9\}</math> or <math>\{1,2,3,4,6,7,9\}</math> or <math>\{1,2,3,5,6,7,8\}</math>. Tilings are not hard to find.
 
Similarly, you can find the other possibilities as <math>\{a_1,a_2,\ldots ,a_7\}=\{1,2,3,4,5,8,9\}</math> or <math>\{1,2,3,4,6,7,9\}</math> or <math>\{1,2,3,5,6,7,8\}</math>. 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: [https://aops.com/community/p2554359]
+
The above solution was posted and copyrighted by WakeUp.
 +
 
 +
 
 +
==Remarks (added by pf02, October 2025)==
 +
 
 +
1. The solution given above is incomplete.  Expressions like
 +
"It's simple from there" and "Tilings are not hard to find"
 +
amount to hand waving rather than a proof or a solution.
 +
 
 +
2. On the discussion page
 +
https://artofproblemsolving.com/community/c6h58591
 +
one can find the solution given above carried to its completion (by
 +
other authors), and other solutions are given, as well as pictures
 +
showing the tilings.
 +
 
 +
 
 +
The original thread for this problem can be found here: [https://aops.com/community/p2554359]
 +
 
  
−
{{alternate solutions}}
 
 
==See Also==
 
==See Also==
  
 
{{IMO box|year=1974|num-b=3|num-a=5}}
 
{{IMO box|year=1974|num-b=3|num-a=5}}
−
[[Category:Olympiad Geometry Problems]]
+
[[Category:Olympiad Combinatorics Problems]]

Latest revision as of 15:10, 7 October 2025

Problem

Consider decompositions of an $8\times8$ chessboard into $p$ non-overlapping rectangles subject to the following conditions:

(i) Each rectangle has as many white squares as black squares.

(ii) If $a_i$ is the number of white squares in the $i$-th rectangle, then $a_1<a_2<\cdots<a_p.$

Find the maximum value of $p$ for which such a decomposition is possible. For this value of $p,$ determine all possible sequences $a_1, a_2, \cdots, a_p.$


Solution

Since each rectangle has the same number of black squares as white squares, $a_1+a_2+\ldots +a_p=\frac{64}{2}=32$. Clearly $a_i\ge i$ for $i=1$ to $i=p$ so $32=a_1+a_2+\ldots + a_p\ge 1+2+\ldots +p=\frac{p(p+1)}{2}$ so this forces $p\le 7$. It is possible to decompose the board into $7$ rectangles, as we will show later. But first let us find all such sequences $a_i$. Now $32-a_7=a_1+a_2+\ldots +a_6\ge 1+2+\ldots +6=21\implies 11\le a_7$. For a rectangle to have $11$ white squares, it will have an area of $22$ so it's dimensions are either $1\times 22$ or $2\times 11$ - neither of which would fit on a $8\times 8$ board. So $a_7\not= 11\implies a_7\le 10$.

If $a_7=10$ (which could fit as a $4\times 5$ rectangle) then $a_1+a_2+\ldots a_6=22$. Then $22-a_6\ge 1+2+\ldots +5=15$ so $7\ge a_6$. So $a_1,a_2,\ldots ,a_6$ are 6 numbers among 1-7. If $1\le k\le 7$ is the number that is not equal to any $a_i$, then $22=a_1+a_2+\ldots +a_7=1+2+\ldots +7-k=28-k$ so $k=6$. Then $a_1=1,a_2=2,a_3=3,a_4=4,a_5=5,a_6=7,a_7=10$. Such a decomposition is possible. Take a $4\times 5$ rectangle on the top left corner, where there are $4$ squares horizontally and $5$ vertically. Then directly below use a $7\times 2,1\times 2$ and a $8\times 1$ rectangle to cover the 3 rows below it. It's simple from there.

Similarly, you can find the other possibilities as $\{a_1,a_2,\ldots ,a_7\}=\{1,2,3,4,5,8,9\}$ or $\{1,2,3,4,6,7,9\}$ or $\{1,2,3,5,6,7,8\}$. Tilings are not hard to find.

The above solution was posted and copyrighted by WakeUp.


Remarks (added by pf02, October 2025)

1. The solution given above is incomplete. Expressions like "It's simple from there" and "Tilings are not hard to find" amount to hand waving rather than a proof or a solution.

2. On the discussion page https://artofproblemsolving.com/community/c6h58591 one can find the solution given above carried to its completion (by other authors), and other solutions are given, as well as pictures showing the tilings.


The original thread for this problem can be found here: [1]


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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1974_IMO_Problems/Problem_4&oldid=262513"