ВсОШ 2022, региональный этап, 11 класс, задача 5
Пусть — -элементное множество, состоящее из натуральных чисел, не превосходящих . Отметим в пространстве все точки, каждая из координат которых принадлежит множеству . К каждой из отмеченных точек прикрепим шарик с написанным на нём числом . На каком наибольшем количестве шариков может быть написано число, равное ?
(П. Козлов)
Ответ
Ответ. .
Решение. Назовём тройку натуральных чисел , элементы которой принадлежат , хорошей, если
Таким образом, нам надо найти наибольшее возможное количество хороших троек.
Выясним, когда тройка хорошая. Перепишем как квадратное уравнение относительно ,
Решая его, получаем
откуда . Иначе говоря, тройка является хорошей тогда и только тогда, когда одно из чисел и равно сумме двух других.
Пусть — все элементы множества . Положим . Оценим количество хороших троек , в которых — наибольшее число, то есть . Заметим, что при любых есть не более одной такой тройки, в которой и (по этим значениям восстанавливается ). Поэтому оцениваемое количество не превосходит количества таких пар чисел , то есть . Аналогично, количества хороших троек, в которых наибольшими являются и , не превосходят . Поэтому общее количество хороших троек не больше .
Эта оценка достигается, если положить , то есть : действительно, тогда при любых найдётся хорошая тройка .
Замечание 1. Можно показать, что для того, чтобы оценка достигалась, необходимо выполнение равенств при всех . Поскольку , приведённый выше пример — единственный.
Замечание 2. Можно показать, что верен следующий факт: равенство при натуральных возможно лишь тогда, когда отношения и являются квадратами рациональных чисел, то есть когда , и при некоторых натуральных и (где ).
В приведённом выше решении этот факт не используется, но в работах некоторые школьники могут на него опираться.