вершины выпуклого многоугольника.

[Samshit]

Условие:
На плоскости отмечено несколько точек. Известно, что любые четыре из них являются вершинами выпуклого четырёхугольника. Докажите, что все отмеченные точки являются вершинами выпуклого многоугольника.

Я нашел контрпример:
Хотя по идеи она должна решаться через доказательство от противного, я после некоторых попыток с данным примером пришел к выводу, что утверждение неверно. Где я допустил ошибку?
P/S На фотографии количество точек равно 8, на пересечении еще одна, прошу прощения, что забыл ее указать, но по рисунку вроде о ней без труда можно догадаться.

[mihaild]

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

[Markiyan Hirnyk]

Увы, это не контрпример. Пусть точки принадлежат решетке $\mathbf{Z}\times \mathbf{Z}$ и их координаты $(0,0),\,(1,0),\,(2,0),\,(0,1),\,(1,1),\,(2,1),\,(0,2),\,(1,2).$ Рассмотрите точки $(0,0),\,(1,2),\,(1,1),\,(2,1).$

[Samshit]

Markiyan Hirnyk
Все, спасибо. Увидел свою ошибку. Тогда, да, это невозможно.

[arseniiv]

Samshit в сообщении #1216081 писал(а):

Тогда, да, это невозможно.

То, что вы в итоге всё-таки не нашли контрпример, ещё не говорит, что его нет. Надо честно доказывать утверждение.

[Samshit]

Хорошо, вот мое доказательство к утверждению. А вы проверьте.

Допустим у нас есть $4n$ точек, любые 4 которые образуют выпуклый четырехугольник. Предположим, что все они не образуют выпуклый многоугольник, тогда при $n=1$ получается, что единственный полученный выпуклый четырехугольник не будет являться выпуклым многоугольником. Противоречие.

[mihaild]

Samshit, вы не можете выбирать произвольное $n$, оно уже задано числом точек (а еще надо рассматривать случаи, когда размер множества точек не делится на $4$).

[Markiyan Hirnyk]

Cм. лемму 2

Цитата:

Лемма 2. Пусть любые четыре из $ n$ точек общего положения на плоскости являются вершинами выпуклого четырехугольника. Тогда эти $n$ точек представляют собой вершины выпуклого $ n$-угольника.

и ее доказательство

Цитата:

Доказательство леммы 2. Достаточно доказать, что выпуклая оболочка n точек плоскости, удовлетворяющих требованиям леммы, является $n$-угольником. Пусть эта выпуклая $ A_1, A_2, …A_m $оболочка представляет собой выпуклый $ m$-угольник с $ m < n$ сторонами. В нашем множестве, состоящем из $n $точек, найдется хотя бы еще одна точка $B$, отличная от вершин выпуклой оболочки. Она лежит внутри многоугольника $ A_1, A_2, …A_m $ и потому попадает внутрь одного из треугольников $A_1 A_2 A_3 , A_1 A_3 A_4 , . . . ,A_1 A_{m-1} A_m$. Пусть точка$B$ лежит внутри треугольника $ A_1 A_i A_{i+1} , 2 \le i \le n - 1$; тогда точки $ A_1, A_i, A_{i+1}, B $ не могут быть вершинами выпуклого четырехугольника, а это противоречит предположению леммы 2. Лемма доказана.

здесь.

[Samshit]

Интуитивно, да и опытным путем, можно понять, что количество точек будет кратным четырем. Как доказать это, у меня есть всего лишь одно предположение. Если выполняется условие, что любые четыре точки являются вершинами четырехугольников, коих $n$ штук, то точек не может быть больше $4n$ и они должны соответственно делится на 4 нацело.

[mihaild]

Samshit в сообщении #1216214 писал(а):

можно понять, что количество точек будет кратным четырем

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

[DeBill]

Markiyan Hirnyk в сообщении #1216213 писал(а):

попадает внутрь одного из треугольников

А почему - внутрь? А если - на сторону?

[grizzly]

DeBill в сообщении #1216225 писал(а):

А почему - внутрь?

Так ведь в этом варианте задачи добавлено условие -- все точки общего положения. Так что -- внутрь.

[Markiyan Hirnyk]

Тогда начнем с вершины $A_2$, рассматривая $A_2 A_3 A_4, A_2 A_4 A_5$ и т. д.

[grizzly]

Markiyan Hirnyk в сообщении #1216229 писал(а):

и т. д.

Представьте себе 5 точек: вершины квадрата плюс пересечение диагоналей. Тогда Maple запарится ходить по кругу

[Markiyan Hirnyk]

Да, надо использовать общее положение точек. Пожалуйста, без выражений типа

Цитата:

Тогда Maple запарится ходить по кругу