ПВГ 2024, 7–8 класс, задача 4
На плоскости расположено точки. Коля проводит замкнутые кривые без самопересечений (произвольной формы) по следующим правилам:
• кривые не пересекаются;
• каждая кривая содержит внутри хотя бы одну точку;
• любые две кривые содержат внутри разные наборы точек.
Какое наибольшее количество таких кривых он сможет провести?
Ответ
Ответ: .
Решение: Очевидно, что для каждой точки есть контур, окружающий ее. Иначе его можно добавить и число кривых увеличится. Также обязательно найдется контур содержащий точки (если все контуры содержат более точек, то его можно добавить внутри контура с точками) «Склеим» две точки, содержащиеся внутри такого контура в одну. Число точек уменьшилось на , а число контуров - на . Проделаем так раза - останется одна точка и один контур. Значит изначально было контуров.