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

Проект МЦНМО
при участии
школы 57
Задача 58117
Тема:    [ Выпуклые многоугольники ]
Сложность: 7
Классы: 8,9
В корзину
Прислать комментарий

Условие

Докажите, что существует такое число N, что среди любых N точек, никакие три из которых не лежат на одной прямой, можно выбрать 100 точек, являющихся вершинами выпуклого многоугольника.

Решение

Мы докажем более общее утверждение. Пусть p, q и r — натуральные числа, причем p, q$ \ge$r. Тогда существует число N = N(p, q, r), обладающее следующим свойством: если все r-элементные подмножества N-элементного множества S произвольным образом разбиты на два непересекающихся семейства $ \alpha$ и $ \beta$, то либо существует p-элементное подмножество множества S, все r-элементные подмножества которого содержатся в $ \alpha$, либо существует q-элементное подмножество, все r-элементные подмножества которого содержатся в $ \beta$ (теорема Рамсея).
Требуемое утверждение легко следует из теоремы Рамсея. В самом деле, пусть N = N(n, 5, 4) и семейство $ \alpha$ состоит из тех четырехэлементных подмножеств N-элементного множества точек, выпуклые оболочки которых — четырехугольники. Тогда существует n-элементное подмножество данного множества точек, выпуклые оболочки любых четырехэлементных подмножеств которого — четырехугольники, так как пятиэлементного подмножества, выпуклые оболочки любых четырехэлементных подмножеств которого — треугольники, не существует (см. задачу 22.2). Остается воспользоваться результатом задачи 22.1.
Докажем теперь теорему Рамсея. Легко проверить, что в качестве N(p, q, 1), N(r, q, r) и N(p, r, r) можно взять числа p + q - 1, q и p соответственно. Докажем теперь, что если p > r и q > r, то в качестве N(p, q, r) можно взять число N(p1, q1, r - 1) + 1, где p1 = N(p - 1, q, r) и  q1 = N(p, q - 1, r). В самом деле, выбросим из N(p, q, r)-элементного множества S один элемент и разобьем (r - 1)-элементные подмножества оставшегося множества S' на два семейства: семейство $ \alpha{^\prime}$ (соответственно $ \beta{^\prime}$) состоит из тех подмножеств, объединения которых с выброшенным элементом входят в семейство $ \alpha$ (соответственно $ \beta$). Тогда либо существует p1-элементное подмножество множества S', все (r - 1)-элементные подмножества которого содержатся в семействе $ \alpha{^\prime}$, либо существует q1-элементное подмножество, все (r - 1)-элементные подмножества которого содержатся в семействе $ \beta{^\prime}$. Рассмотрим первый случай. Так как p1 = N(p - 1, q, r), то либо существует q-элементное подмножество множества S', все r-элементные подмножества которого лежат в $ \beta$ (тогда эти q элементов искомые), либо существует (p - 1)-элементное подмножество множества S', все r-элементные подмножества которого содержатся в $ \alpha$ (тогда эти p - 1 элементов вместе с выброшенным элементом искомые). Второй случай рассматривается аналогично.
Итак, доказательство теоремы Рамсея можно провести индукцией по r, причем при доказательстве шага индукции используется индукция по p + q.

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

книга
Автор Прасолов В.В.
Год издания 2001
Название Задачи по планиметрии
Издательство МЦНМО
Издание 4*
глава
Номер 22
Название Выпуклые и невыпуклые многоугольники
Тема Выпуклые и невыпуклые фигуры
параграф
Номер 1
Название Выпуклые многоугольники
Тема Выпуклые многоугольники
задача
Номер 22.007

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

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