array of ppl

In a rectangular array of people, which will be
taller, the tallest of the shortest people in each
column, or the shortest of the tallest people in each
row?

let's see who gets this one w/o using pen & paper.

shailesh kumar
Friday, March 15, 2002

The shortest of the tallest people. In the worst case, they will be the same.

G.
Friday, March 15, 2002

I agree.  (Just did it in my head.)

Paul Brinkley
Friday, March 15, 2002

It's been a couple of days.  Would one of you guys like to elaborate why this is so?

Paul
Tuesday, March 19, 2002

I derived a proof that shows it will be the tallest of the shortest people.

John Edwards
Tuesday, March 19, 2002

Okay , so here goes..
Ans : The shortest of the tallest ppl in each row is taller.

Proof: Let the tallest of the shortest ppl in each column ( let's call him B ) be in column j.
Let the shortest of the tallest ppl in each row ( let's call him A) be in row i . 
Consider the man standing at array[i][j] ie row = i and col = j ( call him C ) .
Being in row i , C is shorter than A  because A is the tallest in row i. Being in column j , C is taller than B  because B is the shortest in column j. This gives  B < C < A . So A is taller than B.

shailesh kumar
Wednesday, March 20, 2002

  Recent Topics

  Fog Creek Home