ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 98237
Темы:    [ Объединение, пересечение и разность множеств ]
[ Круг, сектор, сегмент и проч. ]
[ Пересекающиеся окружности ]
[ Задачи с ограничениями ]
[ Индукция (прочее) ]
Сложность: 4+
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Фигура Ф представляет собой пересечение 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.

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

олимпиада
Название Турнир городов
Турнир
Номер 16
Дата 1994/1995
вариант
Вариант осенний тур, основной вариант, 8-9 класс
Задача
Номер 7
олимпиада
Название Турнир городов
Турнир
Номер 16
Дата 1994/1995
вариант
Вариант осенний тур, основной вариант, 10-11 класс
Задача
Номер 7

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .