All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 A grid of people (Posted on 2002-07-09)
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?

 See The Solution Submitted by levik Rating: 3.5833 (12 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 The crux of the matter | Comment 12 of 15 |
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

 Search: Search body:
Forums (3)