Arbitrary array of numbers, proof

[Daltohn]

Homework Statement

The numbers 1 to 25 are arranged in a square array of five rows and five columns in an arbitrary way. The greatest number in each row is determined, and then the least number of these five is taken; call that number s. Next, the least number in each column is determined, and then the greatest number of these five is taken; this number is called t.
Prove that s is equal to or greater than t for all possible arrangements.

Homework Equations

The Attempt at a Solution

I see intuitively that this is the case but have no idea where to start with a proof.

 

[BvU]

How about reversing the problem ? assume t > s and show that it leads to a contradiction ...

 

[haruspex]

Suppose it is false, i.e. s<t. What can you say about other numbers in the same row as s?

 

[Daltohn]

Suppose it is false, i.e. s<t. What can you say about other numbers in the same row as s?

I don't know except that they're all less than s. What more can I deduce assuming s<t?

 

[RUber]

s is the least of the biggers and t is the greatest of the smallers, right?
Say, $s = \min( s_1, s_2, s_3, s_4, s_5)$ where $s_n$ denotes the largest member in row n.
Similarly, $t= \max( t_1, t_2, t_3, t_4, t_5)$ where $t_m$ denotes the smallest member in column m.
You know something about row n where $s = s_n$.

I don't know except that they're all less than s.

Use this knowledge to contradict the assumption that s<t.
Each of the t_m terms are the minimums from their columns.

 

[Daltohn]

Okay, I'm an idiot...

Suppose s<t. Then t is not in the same row as s since none of its members is greater than s. But then t can never be the least in its column since every column has a member that is less than or equal to s. However, t is by definition the least in its column. Contradiction. Hence s is greater than or equal to t.

Something like that? Maybe the contradiction is that t both is and isn't a member of the same row as s.

 

[RUber]

You've got it. The best you can hope for is t=s.

 

[Daltohn]

Yep, thank you all :)