Maths Olympiad Prep

Library / /125 of 144

Combinatorics Difficulty 8.8 Shortlist Find the answer

For an integer m1m\geq 1, we consider partitions of a 2m×2m2^m\times 2^m chessboard into rectangles consisting of cells of chessboard, in which each of the 2m2^m cells along one diagonal forms a separate rectangle of side length 11. Determine the smallest possible sum of rectangle perimeters in such a partition.

[i]

A number or a short expression. Spacing and $ signs are ignored.

Solution

To determine the smallest possible sum of rectangle perimeters when a 2m×2m2^m \times 2^m chessboard is partitioned into rectangles such that each of the 2m2^m cells along one diagonal is a separate rectangle, we begin by analyzing the conditions and the required configuration for the partition:

1. Initial Setup:
- Each cell on the diagonal becomes a rectangle of its own. Therefore, there are 2m2^m rectangles, each of size 1×11 \times 1, along the diagonal.
- The perimeter of a 1×11 \times 1 rectangle is 4, hence the combined perimeter for all diagonal rectangles is 4×2m=2m+24 \times 2^m = 2^{m+2}.

2. Partitioning the Rest:
- The goal is to cover the remaining (2m)22m=2m(2m1) (2^m)^2 - 2^m = 2^m(2^m - 1) cells with the fewest rectangles to minimize the sum of the perimeters.
- A simple strategy for minimal perimeter involves using as few rectangles as possible for the non-diagonal part of the chessboard.

3. Optimal Partition Strategy:
- Consider each row and column outside the diagonal as strips. These strips are either horizontal or vertical.
- For a minimal sum, partition the remaining cells into rectangles that span the horizontal or vertical lengths, minimizing cuts that increase perimeter.

4. Calculating Remaining Sums:
- Suppose we can organize these non-diagonal cells into one large rectangle with the remaining dimensions, bearing in mind that each additional cut on the original dimensions introduces additional perimeter.
- However, to maintain the integrity required (that diagonal pieces remain isolated), consider integration of edge rectangular strips appropriately.
- The additional perimeter sum from these constructs must be calculated parallel to the simplest intact remaining shape fitting the non-diagonal area.

5. Ensuring Minimum Perimeter:
- Ultimately, the result follows from covering whole sections of the board optimally, considering that adjoining any necessary strip contributes additive rectangular side lengths.
- Through careful construction and considering a perimeter contribution for structuring, minimizing cross-sections and count focuses perimeters to a lower-bound conjunction.

Finally, by calculating the overall perimeter, factoring diagonally separate minimal perimeter rows/columns and integrally joining larger frame sections minimally, the smallest total possible sum of the perimeters of all rectangles in this configuration is:

2m+2(m+1) \boxed{2^{m+2}(m+1)}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.