Competition problem — Combinatorics

Library / /55 of 92

Combinatorics Difficulty 6.6 National olympiad Prove it Iran

Find the least possible value of $n$ , such that one can place $1, 2, \ldots, n$ in each cell of an $18 \times 18$ table, such that each number is used at least once, and in each row or column, there exist neither two equal nor two consecutive numbers.

Solution

First, we prove that $n = 36$ is not enough. Assume that numbers $1, 2, \ldots, 36$ are assigned to the cells of the table with the described conditions. Since the number $2$ is used, so even numbers (i.e. $2, 4, 6, \ldots, 36$ ) must be put in its row and its column. Similarly, the number $35$ is used, so we have to put odd numbers (i.e. $1, 3, 5, \ldots, 35$ ) in its row and its column. But the intersection of the row containing $35$ and the column containing $2$ has to be odd and even at the same time. Contradiction!

Now it is sufficient to make an example with numbers $1, 2, \ldots, 37$ . In this example, the even numbers are just in the first row, and the other cells are filled with appropriate numbers (just by shifting the odd numbers).

| 2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 | 18 | 20 | 22 | 24 | 26 | 28 | 30 | 32 | 34 | 36 |
|----|----|----|----|----|----|----|----|----|----|----|----|----|----|----|----|----|----|
| 37 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 | 27 | 29 | 31 | 33 |
| 35 | 37 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 | 27 | 29 | 31 |
| 33 | 35 | 37 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 | 27 | 29 |
| 31 | 33 | 35 | 37 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 | 27 |
| 29 | 31 | 33 | 35 | 37 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 |
| 27 | 29 | 31 | 33 | 35 | 37 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 |
| 25 | 27 | 29 | 31 | 33 | 35 | 37 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 |
| 23 | 25 | 27 | 29 | 31 | 33 | 35 | 37 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 |
| 21 | 23 | 25 | 27 | 29 | 31 | 33 | 35 | 37 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 |
| 19 | 21 | 23 | 25 | 27 | 29 | 31 | 33 | 35 | 37 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 |
| 17 | 19 | 21 | 23 | 25 | 27 | 29 | 31 | 33 | 35 | 37 | 1 | 3 | 5 | 7 | 9 | 11 | 13 |
| 15 | 17 | 19 | 21 | 23 | 25 | 27 | 29 | 31 | 33 | 35 | 37 | 1 | 3 | 5 | 7 | 9 | 11 |
| 13 | 15 | 17 | 19 | 21 | 23 | 25 | 27 | 29 | 31 | 33 | 35 | 37 | 1 | 3 | 5 | 7 | 9 |
| 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 | 27 | 29 | 31 | 33 | 35 | 37 | 1 | 3 | 5 | 7 |
| 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 | 27 | 29 | 31 | 33 | 35 | 37 | 1 | 3 | 5 |
| 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 | 27 | 29 | 31 | 33 | 35 | 37 | 1 | 3 |
| 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 | 27 | 29 | 31 | 33 | 35 | 37 | 1 |

Thus, the least possible value of $n$ is $37$ .

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.