Maths Olympiad Prep

Library / /7 of 9

Combinatorics Difficulty 6.5 National olympiad Prove it Austria

Consider arrangements of the numbers 11 through 6464 on the squares of an 8×88 \times 8 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.

Solution

a. This is wrong. For example, one might place the numbers from 11 to 88 along the main diagonal and the numbers from 5757 to 6464 along the secondary diagonal:

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

Therefore the numbers from 11 to 88 are column minima, whereas the numbers from 5757 to 6464 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 aath row and bbth column by F(a,b)F(a, b). Assume that there exist two super-plus-good numbers, and let (i,j)(i, j) and (r,s)(r, s) 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 iri \neq r and jsj \neq s must hold. Then
F(i,j)>F(i,s)(because F(i,j) is row maximum). F(i, j) > F(i, s) \quad (\text{because } F(i, j) \text{ is row maximum}).
F(i,j)<F(r,j)(because F(i,j) is column minimum). F(i, j) < F(r, j) \quad (\text{because } F(i, j) \text{ is column minimum}).
F(r,s)>F(r,j)(because F(r,s) is row maximum). F(r, s) > F(r, j) \quad (\text{because } F(r, s) \text{ is row maximum}).
F(r,s)<F(i,s)(because F(r,s) is column minimum). F(r, s) < F(i, s) \quad (\text{because } F(r, s) \text{ is column minimum}).
These four inequalities lead to the following contradiction:
F(i,j)>F(i,s)>F(r,s)>F(r,j)>F(i,j). F(i, j) > F(i, s) > F(r, s) > F(r, j) > F(i, j).

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.