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

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

Условие

Автор: Карасев Р.

На прямой выбрано 100 множеств A1, A2, .. , A100 , каждое из которых является объединением 100 попарно непересекающихся отрезков. Докажите, что пересечение множеств A1, A2, .. , A100 является объединением не более 9901 попарно непересекающихся отрезков (точка также считается отрезком).

Решение

Пусть множества A и B на прямой являются объединениями m и n отрезков соответственно. Тогда A B – объединение не более m+n-1 отрезков. Ясно, что A B – тоже объединение отрезков. Пусть их количество равно k . Концы отрезков A B являются концами отрезков A или B . Следовательно, рассматривая концы отрезков A B , получаем:

2k 2m+2n. (*)

Но при этом самый левый конец отрезка из всех концов A или B либо не принадлежит A B , либо входит и в концы A и в концы B . Значит, правую часть (*) можно уменьшить на 1. Аналогично, рассматривая самый правый конец A или B , мы уменьшаем правую часть (*) еще на 1. Тогда
2k 2m+2n-2

т.е.
k m+n-1.

Лемма доказана. Теперь решим задачу: пересекая A1 последовательно с A2 , A3 , A100 , мы увидим, что количество отрезков в пересечении будет не более 100+100-1=199 , 199+100-1=298 , 9802+100-1=9901 , что и требовалось доказать.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2001
Этап
Вариант 5
Класс
Класс 10
задача
Номер 01.5.10.2

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

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