Задача
№ 8930
Оценка + пример (экстремальные комбинаторные задачи)
Ур. 5
Олимпиада «Покори Воробьёвы горы!», 9 класс, заключительный этап, 2018, вариант 3b, задача 3
На прямой расположены $16$ точек $A_1, \ldots, A_{16}$, идущие с промежутками 1 см. Миша строит окружности по следующим правилам.
а) Окружности не пересекаются и не касаются.
b) Внутри каждой окружности есть по крайней мере одна из указанных точек $A_1, \ldots, A_{16}$.
c) Ни одна из этих точек не лежит на окружности.
d) Различные окружности содержат внутри себя различные наборы точек. Т. е., например, если какая-то окружность содержит точки $A_1$ и $A_2$ внутри, а остальные снаружи, то вторую окружность, содержащую только $A_1$ и $A_2$ внутри, построить уже нельзя.
Какое наибольшее количество окружностей Миша сможет построить по этим правилам?
а) Окружности не пересекаются и не касаются.
b) Внутри каждой окружности есть по крайней мере одна из указанных точек $A_1, \ldots, A_{16}$.
c) Ни одна из этих точек не лежит на окружности.
d) Различные окружности содержат внутри себя различные наборы точек. Т. е., например, если какая-то окружность содержит точки $A_1$ и $A_2$ внутри, а остальные снаружи, то вторую окружность, содержащую только $A_1$ и $A_2$ внутри, построить уже нельзя.
Какое наибольшее количество окружностей Миша сможет построить по этим правилам?
Ответ:
Решение: