ВсОШ 2023, 8 класс, задача 4

Ответ: (а) ; (б) .

Решение. (а) В любом столбце может быть не более одного отрицательного числа, поэтому всего отрицательных чисел не больше . Их может быть ровно , если, например, сверху стоят числа , , , , , а под ними — числа , , , , соответственно.

(б) Докажем, что каждое из чисел в нижней строке встречается не более раз.

• Пусть в нижней строке встретилось число . Тогда оно не может быть чьим-то квадратом, и над ним написано число . Поскольку в верхней строке все числа различны, то число в нижней строке встречается не более раза.
• Пусть в нижней строке встретилось число . Если в столбце с числом верхнее число является квадратом нижнего, то над ним написано число . Если же нижнее число является квадратом верхнего, то над ним написано или . Поскольку в верхней строке все числа различны, то число в нижней строке встречается не более раз.

Поскольку каждое из чисел в нижней строке встречается не более раз, а чисел там всего , то среди них различных не меньше , т. е. их не меньше .

Осталось привести пример того, как в нижней строке может оказаться ровно различных чисел. Рассмотрим наименьших простых чисел: . Пусть в первых трёх столбцах снизу везде написано число , а сверху написаны числа , и . Аналогично в следующих трёх столбцах снизу везде написано число , а сверху написаны числа , и и так далее. В последних двух столбцах снизу написано число , а сверху написаны числа и .