Problem 1631

Оценка. Докажем, что в первой строке таблицы, в которой числа расставлены по правилам, не менее трёх рациональных чисел (и, соответственно, не более $2016$ иррациональных чисел). Каждое из чисел, встречающихся в таблице, записано ровно в двух клетках, одна из которых находится в верхней строке, а другая — в нижней. Рассмотрим некоторый столбец, пусть в его верхней клетке стоит число $a_1$, а в нижней — $a_2$ (далее коротко обозначаем такой столбец $(a_1, a_2)$). Покрасим столбец $(a_1, a_2)$. Найдём столбец, у которого число $a_2$ находится в верхней клетке, и покрасим его. Если этот столбец — $(a_2, a_1)$, то завершим процесс. Иначе, если этот столбец — $(a_2, a_3)$, где $a_3 \ne a_1$, продолжим: покрасим столбец, у которого число $a_3$ находится в верхней клетке, и т. д. — пока не дойдём до столбца, у которого в нижней клетке находится $a_1$ (это обязательно произойдёт, поскольку числа, равные $a_2, a_3, \dots$, красятся парами). По окончании процесса получим множество покрашенных столбцов $(a_1, a_2), (a_2, a_3), \dots, (a_k, a_1)$, которое назовём циклом длины $k$. Если остались ещё непокрашенные столбцы, выделим ещё один цикл, и т. д. В конечном итоге множество всех столбцов таблицы разобьётся на непересекающиеся циклы. Так как сумма длин всех циклов равна $2019$, найдётся цикл нечетной длины.

Рассмотрим этот цикл: $(a_1, a_2), (a_2, a_3), \dots, (a_{2t+1}, a_1)$, где $t \ge 1$. По условию $a_1+a_2 = b_1, a_2+a_3 = b_2, \dots, a_{2t+1}+a_1 = b_{2t+1}$, где все $b_i$ — рациональные числа. Тогда
$$2a_1 = (a_1 + a_2) - (a_2 + a_3) + (a_3 + a_4) - \dots - (a_{2t} + a_{2t+1}) + (a_{2t+1} + a_1) = b_1 - b_2 + b_3 - \dots - b_{2t} + b_{2t+1}$$
— рациональное число, поэтому $a_1$ рационально. Аналогично, все числа $a_1, a_2, \dots, a_{2t+1}$ рациональны, и их не менее $2t+1 \ge 3$.

Пример. Приведём пример таблицы, заполненной по правилам, в верхней строке которой $2016$ иррациональных чисел:

| 1 | 2 | 3 | $1 + \sqrt{2}$ | $1 - \sqrt{2}$ | $2 + \sqrt{2}$ | $2 - \sqrt{2}$ | ... | $1008 + \sqrt{2}$ | $1008 - \sqrt{2}$ |
|---|---|---|----------------|----------------|----------------|----------------|-----|-------------------|-------------------|
| 2 | 3 | 1 | $1 - \sqrt{2}$ | $1 + \sqrt{2}$ | $2 - \sqrt{2}$ | $2 + \sqrt{2}$ | ... | $1008 - \sqrt{2}$ | $1008 + \sqrt{2}$ |

Замечание. Заметим, что условие нечётности длины строки таблицы существенно. Для чётной длины строки нетрудно построить примеры таблиц, в которых все числа иррациональны.
Условие того, что число не стоит под самим собой, также важно, иначе мог бы появиться цикл длины $1$, и ответ в задаче стал бы равен $2018$.