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"

(Created page with "==Problem== Consider decompositions of an <math>8\times8</math> chessboard into <math>p</math> non-overlapping rectangles subject to the following conditions: (i) Each rectan...")
 
Line 9: Line 9:
  
 
==Solution==
 
==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>.
 +
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>.
  
 +
If <math>a_7=10</math> (which could fit as a <math>4\times 5</math> rectangle) then <math>a_1+a_2+\ldots a_6=22</math>. Then <math>22-a_6\ge 1+2+\ldots +5=15</math> so <math>7\ge a_6</math>. So <math>a_1,a_2,\ldots ,a_6</math> are 6 numbers among 1-7. If <math>1\le k\le 7</math> is the number that is not equal to any <math>a_i</math>, then <math>22=a_1+a_2+\ldots +a_7=1+2+\ldots +7-k=28-k</math> so <math>k=6</math>. Then <math>a_1=1,a_2=2,a_3=3,a_4=4,a_5=5,a_6=7,a_7=10</math>. Such a decomposition is possible. Take a <math>4\times 5</math> rectangle on the top left corner, where there are <math>4</math> squares horizontally and <math>5</math> vertically. Then directly below use a <math>7\times 2,1\times 2</math> and a <math>8\times 1</math> rectangle to cover the 3 rows below it. It's simple from there.
 +
 +
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.
 +
 +
 +
{{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 Geometry Problems]]

Revision as of 14:59, 29 January 2021

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.


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