# Arbitrary array of numbers, proof

1. Oct 9, 2015

### Daltohn

1. The problem statement, all variables and given/known data
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.

2. Relevant equations

3. The attempt at a solution
I see intuitively that this is the case but have no idea where to start with a proof.

2. Oct 9, 2015

### BvU

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

3. Oct 9, 2015

### haruspex

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

4. Oct 9, 2015

### Daltohn

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

5. Oct 9, 2015

### 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$.
Use this knowledge to contradict the assumption that s<t.
Each of the t_m terms are the minimums from their columns.

6. Oct 9, 2015

### 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.

7. Oct 9, 2015

### RUber

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

8. Oct 9, 2015

### Daltohn

Yep, thank you all :)