Question 1019877: The natural numbers 1 ≤ n ≤ 25 are arranged in a square array of five rows and five
columns in an arbitrary manner. The greatest member of each row is selected and s denotes the least
of these. Similarly, the least member in each column is selected and t denotes the greatest of these.
Construct an example in which s not equal to t, and show that s ≥ t always. [Hint: Find x such that s ≥ x and
x ≥ t.]
Answer by richard1234(7193)   (Show Source):
You can put this solution on YOUR website! A very simple example:
[01 02 03 04 10]
[06 07 08 09 05]
[11 12 13 14 15]
[16 17 18 19 20]
[21 22 23 24 25]
(essentially numbering in increasing order, left-right, top-down, except I swapped 5 and 10). Here, s = 9, and t = 4.
Here is one way to prove that  :
Proof: Given the grid, color the greatest number in each row blue and the smallest number in each column red. Note that this could allow certain cells to be both red and blue. We will show that every blue number is at least as large as every red number.
For any two given blue and red numbers, if they are equal (i.e. the cell is both red and blue), then the statement is true. Otherwise, if they are in the same row or column, then the larger number must be blue (otherwise it would violate our coloring). Otherwise, the blue and red numbers are in different rows and columns. If this is the case, then let x be the number in the same row as blue, and the same column as red. It follows that BLUE > x, since x and BLUE are in the same row, and BLUE is the largest number in that row. Similarly, x > RED because RED is the smallest number in that column. Therefore BLUE > RED in this case.
In any case, we have shown that any blue number is at least as large as any red number, so , since s is a blue number and t is a red number.
|
|
|
