Информация о задаче

Задача 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(p₁, q₁, r - 1) + 1, где p₁ = N(p - 1, q, r) и q₁ = N(p, q - 1, r). В самом деле, выбросим из N(p, q, r)-элементного множества S один элемент и разобьем (r - 1)-элементные подмножества оставшегося множества S' на два семейства: семейство $\alpha{^\prime}$ (соответственно $\beta{^\prime}$ ) состоит из тех подмножеств, объединения которых с выброшенным элементом входят в семейство $\alpha$ (соответственно $\beta$ ). Тогда либо существует p₁-элементное подмножество множества S', все (r - 1)-элементные подмножества которого содержатся в семействе $\alpha{^\prime}$ , либо существует q₁-элементное подмножество, все (r - 1)-элементные подмножества которого содержатся в семействе $\beta{^\prime}$ . Рассмотрим первый случай. Так как p₁ = 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