Задача 98237
|
|
 |
Условие
Фигура Ф представляет собой пересечение n кругов (n ≥ 2, радиусы не обязательно одинаковы). Какое максимальное число криволинейных "сторон" может иметь фигура Ф? (Криволинейная сторона – это участок границы Ф, принадлежащий одной из окружностей и ограниченный точками пересечения с другими окружностями.)
Решение
Занумеруем круги числами от 1 до n. Нумерация сторон Ф представляет собой круговую расстановку этих чисел (с повторениями), удовлетворяющую след. условиям:а) два одинаковых числа не стоят рядом;
б) нет фрагментов вида ...a...b...a...b... .
Действительно, рассмотрим две дуги AB, ограничивающие пересечение кругов a и b. Если взять две точки A1 и A2 на одной из них (принадлежащей границе круга a) и две точки B1 и B2 – на другой, то хорды A1A2 и B1B2, очевидно, не пересекаются.
Индукцией по n докажем, что длина l такой расстановки не превосходит 2n – 2.
База (n = 2) очевидна.
Шаг индукции. Если все числа встречаются не более одного раза, то все в порядке: n ≤ 2n – 2.
Пусть одно из чисел (a) встретилось k > 1 раз. Разорвем расстановку в этих местах и из каждой части составим свою расстановку, "склеив" концы. Все они удовлетворяют указанным условиям, значит, длина li i-й расстановки не больше 2ni – 2. Кроме того, в этих расстановках нет общих чисел, отличных от a. Поэтому, сложив, получим l ≤ 2(n + k – 1) – 2k = 2n – 2. Расстановки длины 2n – 2 существуют, например, 1, 2, ..., n–1, n, n–1, ..., 2 или 1, n, 2, n, ..., n–1, n.
Нетрудно построить примеры фигур Ф, соответствующих этим расстановкам.
Ответ
2n – 2 стороны.
Замечания
1. Баллы: 8-9 кл – 9, 10-11 кл. – 8.
2. Ср. с зад. 116769.
