Учитель собирается дать детям задачу следующего вида. Он сообщит им, что он задумал многочлен P(x) степени 2017 с целыми коэффициентами, старший коэффициент которого равен 1. Затем он сообщит им k целых чисел n₁, n₂, ..., n_k и отдельно сообщит значение выражения  P(n₁)P(n₂)...P(n_k).  По этим данным дети должны найти многочлен, который мог бы задумать учитель. При каком наименьшем k учитель сможет составить задачу такого вида так, чтобы многочлен, найденный детьми, обязательно совпал бы с задуманным?

   Решение

На плоскости дано n3 точек. Пусть d — наибольшее расстояние между парами этих точек. Докажите, что имеется не более n пар точек, расстояние между которыми равно d.

   Решение

Тема:    [ Системы точек ]

Сложность: 5+ Классы: 8,9

Прислать комментарий

Условие

На плоскости дано n3 точек. Пусть d — наибольшее расстояние между парами этих точек. Докажите, что имеется не более n пар точек, расстояние между которыми равно d.

Решение

Назовем диаметром отрезок длиной d, соединяющий пару данных точек. Концы всех диаметров, выходящих из точки A, лежат на окружности с центром A и радиусом d. Так как расстояние между любыми двумя точками не превосходит d, концы всех диаметров, выходящих из A, лежат на дуге, угловая величина которой не превосходит 60^o. Следовательно, если из точки A выходят три диаметра AB, AC и AD, то один из концов этих диаметров лежит внутри угла, образованного двумя другими. Пусть для определенности точка C лежит внутри угла BAD. Докажем, что тогда из точки C выходит не более одного диаметра. Предположим, что есть еще диаметр CP и точки B и P лежат по разные стороны от прямой AC (рис.). Тогда ABCP — выпуклый четырехугольник, поэтому AB + CP < AC + BP (см. задачу 9.14), т. е. d + d < d + BP, а значит, BP > d, чего не может быть.
В итоге получаем, что либо из каждой точки выходит не более двух диаметров, либо существует точка, из которой выходит не более одного диаметра. Теперь требуемое утверждение можно доказать индукцией по числу точек. Для n = 3 оно очевидно. Предположим, что утверждение доказано для любой системы из n точек, и докажем его для системы из n + 1 точки. В этой системе либо есть точка, из которой выходит не более одного диаметра, либо из каждой точки выходит не более двух диаметров. В первом случае отбрасываем эту точку и, воспользовавшись тем, что в оставшейся системе не более n диаметров, получаем требуемое. Второй случай очевиден.

Источники и прецеденты использования