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?
Answer: height(A) ≥ height(B)
Notation:
If the people are arranged in a grid consisting of i rows and j columns, then define the matrix M as the "height" matrix composed of i rows and j columns where the elements of the matrix, denoted by m(a,b), record the height of the person in the a_th row and the b_th column.
Proof:
1) Choose A and B from the matrix according to the rules and denote A=m(a,b) and B=m(c,d).
2) Since A is by definition bigger than any other element in it's row, m(a,b) ≥ m(a,d).
3) Since B is by definition smaller than any other element in it's column, m(a,d) ≥ m(c,d).
4) Stringing together the inequalities:
height(A)=m(a,b) ≥ ;m(a,d) ≥ m(c,d)=height(B).
Q.E.D.
Notes: This may seem like trickery, but it's not. Because of the way the 'tallest of row' and 'shortest of column' groups are chosen, they can be related throught the matrix element where the row A is in and the column B is in intersect.
The elements of the the part about the shortest of the tallest and the tallest of the shortest is there to confuse you a bit. in fact, I've proven that is that all the tallest elements of the rows are taller than all the shortest people in the columns - a more general result.
Four line proof:
