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 16: Line 16:
 
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]
  
 
{{alternate solutions}}
 
{{alternate solutions}}

Latest revision as of 15:03, 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.

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