Let $n$ be a positive integer. Mariano divides a rectangle into $n^2$ smaller rectangles by drawing $n-1$ vertical lines and $n-1$ horizontal lines, parallel to the sides of the larger rectangle. On every step, Emilio picks one of the smaller rectangles and Mariano tells him its area. Find the least positive integer $k$ for which it is possible that Emilio can do $k$ conveniently thought steps in such a way that with the received information, he can determine the area of each one of the $n^2$ smaller rectangles.
Problem
Source:
Tags: combinatorics
socrates
17.11.2015 20:01
Any ideas?
mssmath
18.11.2015 01:20
Notice that there are $2n$ independent variables which determine the configuration (The distance between adjacent lines and the sides vertically and horizontally). I claim that the areas constitute a system of $2n-1$ independent variables. The easiest way of showing this is to take the area of the bottom corner rectangles and compare the area to those on the left and right sides. If one of these ratios is not "known" then configuration can easily shown not to be unique. This gives $2n-2$ ratios plus the area of the lower rectangle so $2n-2$ independent variables. This necessitates knowing at least $2n-1$ areas (as this gives at most $2n-1$ independent equations.) Otherwise we have $2n-1$ independent variables and less equations and therefore an underdetermined system. $2n-1$ such rectangles that can be selected to determine the rest are the rectangles on the bottom and or top side. In particular a rectangle in the middle of this configuration has area equal to that of the product of the area below it on the bottom edge and to the left of it on the left edge divided by the area of the bottom-left corner rectangle. The result follows.