Track / Stage 6 / 252 of 400 #1732 of 2444

Problem 1732

National Olympiad, first round

Combinatorics Difficulty 6.6 Prove it Iranian Mathematical Olympiad · 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.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official 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

37

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.

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

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

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