Every rectangle is formed from a number of full squares

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Every rectangle is formed from a number of full squares

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: IMO ShortList 1974, Bulgaria 1, IMO 1997, Day 2, Problem 1

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3647 posts

orl

#1 h Oct 29, 2005, 11:04 PM • 4 Y

Y by Adventure10, Mango247, ItsBesi, cubres

Consider decompositions of an $8\times 8$ 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<\ldots <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,\ldots ,a_p$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1347 posts

WakeUp

#2 h Dec 27, 2011, 4:41 PM • 3 Y

Y by sohere, Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

768 posts

#3 h Aug 30, 2016, 8:22 AM • 2 Y

Y by Adventure10, Mango247

This post has been edited 1 time. Last edited by quangminhltv99, Aug 30, 2016, 8:29 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6882 posts

#4 h Dec 21, 2023, 7:10 PM • 1 Y

Y by MS_asdfgzxcvb

Here's an illustration of all four tilings.
Source code

size(13cm);
picture g;
for (int i=0; i<8; ++i) {
  for (int j=0; j<8; ++j) {
    if ((i+j)#2 == (i+j)/2) {
      fill(g, shift(i,j)*unitsquare, rgb("cccccc"));
    }
  }
}

picture p1, p2, p3, p4;
add(p1, g);
add(p2, g);
add(p3, g);
add(p4, g);
label(p1, "$64 = 2 + 4 + 6 + 10 + 12 + 14 + 16$", (4,0), dir(-90));
label(p2, "$64 = 2 + 4 + 6 + 8 + 12 + 14 + 18$", (4,0), dir(-90));
label(p3, "$64 = 2 + 4 + 6 + 8 + 10 + 16 + 18$", (4,0), dir(-90));
label(p4, "$64 = 2 + 4 + 6 + 8 + 10 + 14 + 20$", (4,0), dir(-90));

pen r = heavyred+1.4+fontsize(16pt);
pen[] colors = {
  green, orange, yellow, blue, purple,
  lightred, cyan, darkcyan, olive, fuchsia
};
void draw_rect(picture p, int x1, int y1, int x2, int y2) {
  int a = abs((y2-y1)*(x2-x1));
  filldraw(p, box((x1,y1),(x2,y2)), opacity(0.2)+colors[a#2-1], r);
  label(p, "\textbf{" + (string) a + "}", ((x1+x2)/2, (y1+y2)/2), r);
}
draw_rect(p1, 0,6, 1,8);
draw_rect(p1, 1,6, 8,8);
draw_rect(p1, 0,4, 2,6);
draw_rect(p1, 2,4, 8,6);
draw_rect(p1, 0,2, 3,4);
draw_rect(p1, 3,2, 8,4);
draw_rect(p1, 0,0, 8,2);

draw_rect(p2, 0,6, 1,8);
draw_rect(p2, 1,6, 8,8);
draw_rect(p2, 0,4, 2,6);
draw_rect(p2, 2,4, 8,6);
draw_rect(p2, 0,1, 2,4);
draw_rect(p2, 2,1, 8,4);
draw_rect(p2, 0,0, 8,1);

draw_rect(p3, 0,6, 1,8);
draw_rect(p3, 1,6, 3,8);
draw_rect(p3, 3,6, 8,8);
draw_rect(p3, 0,4, 8,6);
draw_rect(p3, 0,1, 2,4);
draw_rect(p3, 2,1, 8,4);
draw_rect(p3, 0,0, 8,1);

draw_rect(p4, 0,6, 1,8);
draw_rect(p4, 1,6, 8,8);
draw_rect(p4, 2,1, 4,6);
draw_rect(p4, 0,4, 2,6);
draw_rect(p4, 0,1, 2,4);
draw_rect(p4, 4,1, 8,6);
draw_rect(p4, 0,0, 8,1);

pen border = black+1.5;
draw(p1, box((0,0), (8,8)), border);
draw(p2, box((0,0), (8,8)), border);
draw(p3, box((0,0), (8,8)), border);
draw(p4, box((0,0), (8,8)), border);

real w = 9.5;
add(shift(0,0)*p1);
add(shift(w,0)*p2);
add(shift(0,-w)*p3);
add(shift(w,-w)*p4);

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1758 posts

#5 h Jan 4, 2024, 3:22 AM

Y by

We claim that the answer is $\boxed{p = 7},$ achieved with $(a_1,a_2,a_3,a_4,a_5,a_6,a_7) = (1,2,3,4,5,8,9),(1,2,3,4,5,7,10), (1,2,3,4,6,7,9),(1,2,3,5,6,7,8).$

First note that $p \le 7$ since otherwise $2(a_1+a_2+\dots+a_p) \ge 2(1+2+\dots + 8) \ge 72 > 64,$ which is a clear contradiction. For $p = 7,$ the only possible ordered tuples $(a_1,a_2,a_3,a_4,a_5,a_6,a_7)$ such that $a_1 < a_2 < a_3 < a_4 < a_5 < a_6 < a_7$ and $a_1 + a_2 + \dots + a_7 = 32$ are $(a_1,a_2,a_3,a_4,a_5,a_6,a_7) = (1,2,3,4,5,8,9),(1,2,3,4,5,7,10), (1,2,3,4,6,7,9),(1,2,3,5,6,7,8),(1,2,3,4,5,6,11).$ The last tuple does not have a construction since that would require us to have a rectangle of area $22$ with sidelengths less than or equal to $8,$ which is clearly impossible. The other four tuples are possible, as shown by the pictures below, proving our claim.

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

150 posts

Markas

#6 h May 6, 2024, 8:41 AM

Y by

$a_1 < a_2 \cdots < a_p$ . We know that the i-th rectangle has $a_i$ white and $a_i$ black, or $2a_i$ squares altogether. Let $p \geq 8$ $\Rightarrow$ $a_1 \geq 1$ and $a_8 \geq 8$ $\Rightarrow$ $2(a_1 + a_2 + \cdots + a_8) \geq 2(1 + 2 + \cdots + 8) = 2.\frac{8.9}{2} = 72$ but the total number of cells in the table is 8.8 = 64, but since 72 is larger than 64, $p < 8$ . We search for the largest possible p. We showed $p < 8$ $\Rightarrow$ we will prove p = 7 works, and we will find all ordered tuples $(a_1, a_2, a_3, a_4, a_5, a_6, a_7)$ . We want $2(a_1 + \cdots a_7) = 64$ $\Rightarrow$ $a_1 + a_2 \cdots a_7 = 32$ , where $a_1 < a_2 \cdots < a_7$ $\Rightarrow$ the ordered tuples we could get this way are $(a_1, a_2, a_3, a_4, a_5, a_6, a_7) = (1,2,3,4,5,7,10),(1,2,3,4,5,8,9), (1,2,3,4,6,7,9),(1,2,3,5,6,7,8),(1,2,3,4,5,6,11)$ . The last tuple doesn't work, since rectangle with area 22, can be only 2x11, but the largest side of the table is 8. The other tuples are achievable and examples are easily drawn. So the answer is p = 7, achievable with $(a_1,a_2,a_3,a_4,a_5,a_6,a_7) = (1,2,3,4,5,8,9),(1,2,3,4,5,7,10), (1,2,3,4,6,7,9),(1,2,3,5,6,7,8)$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

639 posts

eg4334

#7 h Nov 15, 2024, 1:34 AM • 1 Y

Y by MS_asdfgzxcvb

Ban this problem.
The answer is just $7$ . $8$ is not possible because we need distinct even integers to sum to $64$ by area which is not possible cause $2(1+2+\dots+8) = 72 > 64$ .
So basically we need distinct integers $b_1, b_2, \dots b_7$ s.t. $\sum b_i = 32$ After a check we can just find four viable pairs becuase one has $b_7=11$ which is clearly not possible. The others are possible but I don't know how to asy.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

363 posts

#8 h Feb 16, 2025, 1:55 AM

Y by

The optimum is $p = 7$ , attainable with $(1, 2, 3, 5, 6, 7, 8), (1, 2, 3, 4, 5, 7, 10), (1, 2, 3, 4, 5, 8, 9), (1, 2, 3, 4, 6, 7, 9)$ .
We easily have the bound
$1 + 2 + \dots + p = \dfrac{p(p + 1)}{2} \le a_1 + a_2 + \dots + a_p = 32 \implies p \le 7.$ Now we show attainability at $p = 7$ , by carefully listing the possible tuples our candidates are
$(1, 2, 3, 5, 6, 7, 8), (1, 2, 3, 4, 5, 6, 11), (1, 2, 3, 4, 5, 7, 10), (1, 2, 3, 4, 5, 8, 9), (1, 2, 3, 4, 6, 7, 9).$ Clearly $(1, 2, 3, 4, 5, 6, 11)$ does not work as one of the rectangles would have a side length that is a multiple of $11$ , which cannot exist as we are confined to an $8 \times 8$ grid. It is well-known that a rectangle with even area must have an equal number of white and black squares when checkerboard-colored, below are constructions:

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

648 posts

#9 h Mar 28, 2025, 3:43 PM

Y by

Note that the $i$ -th rectangle will have an area of exactly $2a_i$ . Thus, we need $2(a_1+\dots+a_p)<64\implies p\le 7$ (clearly $2(1+2+\dots+8)=72>64$ ). When $p=7$ , we obtain the following $5$ sequences:
$\begin{align} (1, 2, 3, 5, 6, 7, 8),\\ (1, 2, 3, 4, 5, 6, 11),\\ (1, 2, 3, 4, 5, 7, 10),\\ (1, 2, 3, 4, 5, 8, 9),\\ (1, 2, 3, 4, 6, 7, 9). \end{align}$ Sequence $(2)$ fails because we cannot fit a $1\times 22$ or $2\times 11$ rectangle into the chessboard; constructions exist for the four remaining sequences. $\blacksquare$

This post has been edited 1 time. Last edited by gladIasked, Mar 28, 2025, 3:43 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1803 posts

akliu

#10 h Apr 2, 2025, 4:23 PM

Y by

The largest value of $p$ for which a decomposition could occur is $7$ . For the sake of contradiction, assume that $p=8$ could result in a decomposition. The sequence with smallest sum for $p=8$ is $a_i = i$ for $1 \leq i \leq 8$ . Indeed, this sum is $1+2+\dots+8 = 36$ , meaning that there are $72$ tiles in total that the rectangles must cover. Since we have an $8$ -by- $8$ chessboard, this is impossible. On the other hand, if we have $p=7$ , we have $2(1+2+\dots+7) = 56$ tiles to be covered by the rectangles as a minimum. We now want to figure out all the possible ways to add $8$ more tiles to some of the $7$ rectangles that result in a valid decomposition.

We start caseworking here; by our monotonic sequence condition, we arrive at the following cases that we must check: $(1, 2, 3, 4, 5, 6, 11)$ , $(1, 2, 3, 4, 5, 7, 10)$ , $(1, 2, 3, 4, 5, 8, 9)$ , $(1, 2, 3, 4, 6, 7, 9)$ , and $(1, 2, 3, 5, 6, 7, 8)$ . I don't feel like embedding diagrams in this solution; by the Just Trust In The Process method, it is simple to verify that all of these sequences result in valid decompositions except the first one.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

684 posts

#11 h Apr 25, 2025, 7:41 AM

Y by

I claim that $p = 7$ is the maximum, with the sequences $(1, 2, 3, 5, 6,7, 8), (1, 2, 3,4,6,7,9)$ , $(1, 2, 3, 4,5, 8, 9).$ Since they are all distinct, we must have that $1 + 2 + 3 + \cdots + p \leq 32.$ The maximum $p$ that satisfies this is $p = 7.$

There are 5 different partitions of $32$ into $7$ distinct values: $(1, 2, 3, 5, 6,7, 8), (1, 2, 3,4,6,7,9)$ , $(1, 2, 3, 4,5, 8, 9), (1, 2, 3, 4,5, 6, 11).$ Clearly, the last one doesn't work because it doesn't fit. The others clearly work by seperating them into multiples of 8, and then fitting.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a