Imagine a "grid" of people: some number of people arranged in a number of rows and columns in a rectangular formation.

We designate person A as the shortest person in the group of the tallest people of each row. We then designate person B as the tallest person in the group of shortest people in each column.

Who is taller, A or B?

In the grid, replace each person by a real number. Choose a row and a column. There is exactly one grid position that is both in the chosen row and in the chosen column, and the real number r in that position is no greater than the maximum element M in the chosen row and no less than the minimum element m in the chosen column. Hence m <= r <= M so that m <= M. This is the crux of the matter. Now if we happened to choose the row to contain a minimum M' of the row maxima, and the column to contain a maximum m' of the column minima, we would have m' <= r <= M'. If the real numbers that replace the people are the people's heights, then we have an answer to the problem as originally formulated: A is always at least as tall as B. It is possible for m' = r = M' to occur as with the grid
6 5
5 4
and in this case A = B. In fact, if the heights are all different in the M' row and in the m' column, then clearly A = B whenever m' = r = M'. Since the problem statement seems to imply that there is a unique minimum of the row maxima and a unique maximum of the column minima, we conclude m'=M' if and only if A = B. Thus if interpret the problem statement in this way and also insist that A and B be two different people, A is always strictly taller.









Edited on December 14, 2003, 1:01 am

Posted by Richard on 2003-12-13 23:51:03