A given rectangle $ R$ is divided into $mn$ 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$?
Problem
Source: Hungary-Israel Mathematical Competition 2007 Problem 4
Tags: geometry, rectangle, induction, combinatorics unsolved, combinatorics
SimonM
20.11.2007 22:02
Not sure how to go about proving this but wouldn't it be
WLOG assume $ m \leq n$. Then, by selecting diagonally down, you can ascertain the area of the first section. Call the height the distance fallen. There will be m squares in this. Then the remaining dimensions of the rectangle can be determined from selecting $ n-m$ squares in the remaining horizontal. Hence $ m+(n-m)=n$
zgorkster
21.11.2007 09:16
Hmmm. I may be interpreting the problem wrong, but I think that we are only given each of the small rectangles areas, not the width and length. For instance, if $ m=n=2$, then if I only give you two of the areas, there is no way to determine the area of $ R$. I think the answer is $ m+n-1$. Suppose $ R$ is cut into $ m$ rows and $ n$ columns. Then if we are given an entire row of rectangles' areas and an entire column of rectangles' areas, then it is not hard to see that we can produce the area of $ R$. To show this is optimal, we proceed by induction. We induction on $ m+n$. If $ m=n=1$, the proof is trivial. Now given an $ m\times n$ rectangle, suppose that it could be done with at most $ m+n-2$ areas. Then we know there is a column or row that contains a known area but which not all the areas are known; otherwise, we would have to have at least $ m+n-1$ areas. Without loss of generality, assume that this occurs at the far left column. Then we can swap the rows so that all the known rectangles occur at the top-leftmost part of $ R$. As denoted below, call their union rectangle $ A$. Suppose there are $ 0<a<m$ small rectangles that make up $ A$. Then we can partition $ R$ into four big rectangles $ A,B,C,D$ as shown below: $ \begin{array} [b] {cc} A&B\\ C&D\\ \end{array}$ Consider the bottom-rightmost rectangle $ D$ of dimension $ (m-a)\times (n-1)$. By assumption, there are at most $ m+n-2-a$ known squares in this rectangle. Note, however, that we have no information about $ C$, and so if we do not know $ D$, there is no possible way to obtain $ R$ by the induction hyopthesis. But by the induction hyopthesis, we need at least $ m+n-a-2$ areas in $ D$ to determine its area, and thus all remaining $ m+n-a-2$ squares must be in $ D$. But this means that none are in $ B$, and so we do not know either $ B$ or $ C$. Hence by the induction hypothesis, we cannot determine $ R$ again. Thus we need at least $ m+n-1$ areas, and this completes the induction. This proof may require that the $ 2\times 2$ case is proved first, but this is really not that difficult.