Skip to main content
OlympiadHQ

Browse · MathNet

Print

National 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.
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:
19101112131457
152161718195820
212232324592526
272829460303132
333435615363738
394062414264344
456346474849750
645152535455568
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:

Techniques

OtherMatrices