Maths Olympiad Prep

Track / Stage 6 / 244 of 400 #1244 of 1964

Problem 1244

National olympiad, first round
Combinatorics Difficulty 6.4 Find the answer

A given rectangle R R is divided into mnmn small rectangles by straight lines parallel to its sides. (The distances between the parallel lines may not be equal.) What is the minimum number of appropriately selected rectangles’ areas that should be known in order to determine the area of R R?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Official solution

1. Understanding the Problem:
We are given a rectangle R R divided into mn mn smaller rectangles by lines parallel to its sides. The goal is to determine the minimum number of these smaller rectangles' areas that need to be known to determine the area of R R .

2. Initial Consideration:
If m=n=2 m = n = 2 , we have a 2×2 2 \times 2 grid of smaller rectangles. Knowing only two of these areas is insufficient to determine the area of R R because the dimensions of the rectangles are not necessarily equal.

3. General Case:
Suppose R R is divided into m m rows and n n columns. We need to find the minimum number of known areas to determine the area of R R .

4. Hypothesis:
The hypothesis is that the minimum number of known areas required is m+n1 m + n - 1 .

5. Induction Basis:
For m=1 m = 1 and n=1 n = 1 , the problem is trivial since knowing the area of the single rectangle directly gives the area of R R .

6. Induction Step:
Assume the hypothesis holds for all rectangles divided into (m1)×n (m-1) \times n or m×(n1) m \times (n-1) smaller rectangles. We need to show it holds for an m×n m \times n rectangle.

7. Partitioning the Rectangle:
Consider the m×n m \times n rectangle divided into four parts:
ABCD \begin{array}{cc} A & B \\ C & D \\ \end{array}
where A A is an a×b a \times b rectangle, B B is an a×(nb) a \times (n-b) rectangle, C C is an (ma)×b (m-a) \times b rectangle, and D D is an (ma)×(nb) (m-a) \times (n-b) rectangle.

8. Known Areas:
By the induction hypothesis, we need at least (a+b1) (a + b - 1) known areas to determine the area of A A , and similarly for B B , C C , and D D .

9. Combining Information:
To determine the area of R R , we need to know the areas of at least one row and one column of smaller rectangles. This gives us m+n1 m + n - 1 known areas.

10. Optimality:
If fewer than m+n1 m + n - 1 areas are known, there will be at least one row or one column with no known areas, making it impossible to determine the area of R R .

11. Conclusion:
By induction, the minimum number of known areas required to determine the area of R R is m+n1 m + n - 1 .

\blacksquare

The final answer is m+n1 \boxed{ m + n - 1 } .

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