Browse · MathNet
PrintNational Competition
Austria counting and probability
Problem
Consider arrangements of the numbers through on the squares of an chess board, where each square contains exactly one number and each number appears exactly once. A number in such an arrangement is called super-plus-good, if it is the largest number in its row and at the same time the smallest number in its column. Prove or disprove each of the following statements:
a. Each such arrangement contains at least one super-plus-good number.
b. Each such arrangement contains at most one super-plus-good number.
a. Each such arrangement contains at least one super-plus-good number.
b. Each such arrangement contains at most one super-plus-good number.
Solution
a. This is wrong. For example, one might place the numbers from to along the main diagonal and the numbers from to along the secondary diagonal:
Therefore the numbers from to are column minima, whereas the numbers from to are row maxima. Therefore, no number is at the same time column minimum and row maximum, so no number is super-plus-good.
b. This is true. Denote the number in the th row and th column by . Assume that there exist two super-plus-good numbers, and let and be the coordinates of these two numbers. Since all numbers are different, the row maxima and column minima are unique. Therefore no row and no column may contain more than one super-plus-good number, so and must hold. Then These four inequalities lead to the following contradiction:
| 1 | 9 | 10 | 11 | 12 | 13 | 14 | 57 |
|---|---|---|---|---|---|---|---|
| 15 | 2 | 16 | 17 | 18 | 19 | 58 | 20 |
| 21 | 22 | 3 | 23 | 24 | 59 | 25 | 26 |
| 27 | 28 | 29 | 4 | 60 | 30 | 31 | 32 |
| 33 | 34 | 35 | 61 | 5 | 36 | 37 | 38 |
| 39 | 40 | 62 | 41 | 42 | 6 | 43 | 44 |
| 45 | 63 | 46 | 47 | 48 | 49 | 7 | 50 |
| 64 | 51 | 52 | 53 | 54 | 55 | 56 | 8 |
b. This is true. Denote the number in the th row and th column by . Assume that there exist two super-plus-good numbers, and let and be the coordinates of these two numbers. Since all numbers are different, the row maxima and column minima are unique. Therefore no row and no column may contain more than one super-plus-good number, so and must hold. Then These four inequalities lead to the following contradiction:
Techniques
OtherMatrices