Задача 79409

Темы:    [ Системы точек ] [ Неравенство треугольника (прочее) ]

Сложность: 4- Классы: 8

Условие

Какое наименьшее количество точек на плоскости надо взять, чтобы среди попарных расстояний между ними встретились числа 1, 2, 4, 8, 16, 32, 64?

Решение

Ответ: 8 точек.
Очевидно, что 8 точек A₁, A₂, ..., A₈, расположенных на расстояниях A₁A₂ = 1, A₂A₃ = 2, ..., A₇A₈ = 64, удовлетворяют условию. Покажем, что меньшего числа точек на плоскости расположить нельзя. Для каждого k = 0, 1,..., 6 выберем пару точек, между которыми расстояние равно 2^k, и соединим их отрезками. Из неравенства треугольника следует, что полученные 7 отрезков (и никакая часть из них) не образуют замкнутого многоугольника. Следовательно, число точек должно по крайней мере на 1 превосходить число этих отрезков, т. е. быть не меньшим 7 + 1 = 8.

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

олимпиада
Название	Московская математическая олимпиада
год
Номер	45
Год	1982
вариант
Класс	7
задача
Номер	4