Теорема Хелли для целочисленной решетки.

[VVV]

  На самом деле задача для двумерного случая сводится к доказательству следующего факта. Для любого целого (вершины в узлах двумерной целочисленной решетки) выпуклого 5-угольника найдется целая точка внутри или на границе "внутреннего" пятиугольника. Этот факт можно доказать от противного, если рассмотреть такой пятиугольник с минимальной площадью (это возможно в силу теоремы Пика). А как же быть в трехмерном случае?

[Sirion]

Путаница автора (см. страницу 1) наводит на определённые размышления. Известно ли корректное решение ему самому?

[VVV]

   Я знаю источник, в котором доказывается эта теорема.

[Sirion]

Понятненько. Честно говоря, задача выглядит так, будто для её решения нужны какие-то узкоспециальные, малоизвестные вещи (менее известные, чем теорема Пика, например).

[VVV]

  Для двумерного случая знать почти ничего не надо.  Но теорема доказывается для любой конечной размерности. А вот как доказать ручками для трех размерностей? Это вопрос!

[Sirion]

В двумерном случае нам требуется показать, что для целого выпуклого пятиугольника существует целая точка, принадлежащая "внутреннему" пятиугольнику (ограниченному диагоналями исходного). Будь я проклят, если мне это очевидно.

[VVV]

   Это несложно. Это следует из тех же соображений, что и в оригинальной теореме Хелли.

[Sirion]

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

[VVV]

   Двумерный случай. Сначала доказывается для 5 множеств. Затем по индукции распространяется на произвольное конечное число множеств. Для случая 5 множеств возьмем пять точек из пересечения всех множеств кроме i-го. Это и есть условный пятиугольник. Если он не является выпуклым или вершины совпадают, то все ясно. Остается доказать для выпуклого пятиугольника. Все равно это нужно доказывать для случая, когда i-ое множество является выпуклой оболочкой всех 5 вершин  этого пятиугольника кроме i-ой.

[Sirion]

Милейший, Вы говорите очевидные вещи. Я их прекрасно понимаю. Но они не являются ответом на мой вопрос. Наоборот, они-то к этому вопросу и приводят.
Пусть у нас есть пять точек, ни одна из которых не является выпуклой комбинацией других. Итое множество ограничивается выпуклой оболочкой всех точек, кроме итой. Нам нужно доказать, что пересечение итых множеств для и от одного до пяти содержит хотя бы одну целую точку. То есть:

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

Так как это доказать?

[VVV]

   Это неунылая, но решаемая задача.

[Sirion]

Уверен, что так. Вопрос в том, элементарно ли она решаема. Меня таки мучает определённое недоверие к автору. В этой теме он уже блеснул умом и сообразительностью.

Да, ещё вопрос...

  На самом деле задача для двумерного случая сводится к доказательству следующего факта. Для любого целого (вершины в узлах двумерной целочисленной решетки) выпуклого 5-угольника найдется целая точка внутри или на границе "внутреннего" пятиугольника. Этот факт можно доказать от противного, если рассмотреть такой пятиугольник с минимальной площадью (это возможно в силу теоремы Пика).

Если я правильно понимаю, что здесь понимается под "внутренним" пятиугольником - как мы можем применить к нему теорему Пика, если у него (в общем случае) нецелые вершины?

[VVV]

   Задача решаема элементарно. Просто, сначала двумерный случай разобрал быстро, но неправильно. Теорема Пика там не нужна.
    Пока есть возможность блеснуть умом и сообразительностью. А вечером будет дано элементарное решение.

[Sirion]

Да, действительно.
Выпуклый пятиугольник разбивается диагоналями на одиннадцать областей: внутренний пятиугольник, пять треугольников, к нему примыкающих (далее - треугольники типа А) и пять других треугольников (далее - типа Б).
Пусть существует целый выпуклый пятиугольник, у которого внутренний пятиугольник не содержит целых точек. Если в одном из треугольников типа А содержится целая точка, мы можем переместить туда инцидентную ему вершину, при этом новый внутренний пятиугольник лежит строго внутри прежнего, а количество целых точек, принадлежащих исходному, уменьшится.
Если в треугольниках типа А целых точек также нет, но есть в треугольнике типа Б, мы можем переместить туда любую из двух инцидентных вершин, при этом внутренний пятиугольник останется внутри "звезды" (в которой, по допущению, целых точек уже нет), а количество целых точек исходного пятиугольника опять же уменьшится.
При обоих этих преобразованиях сохраняется выпуклость.
В силу конечности количества целых точек исходного пятиугольника мы, повторяя эти действия, придём к ситуации, когда ни внутри, ни на границах исходного пятиугольника не осталось целых точек.
По теореме Пика площадь каждого из треугольников, образованных тройками его вершин, равна 0.5. Из этого следует, что если рассмотреть три треугольника с общим основанием, их высоты будут равны, а значит, три вершины пятиугольника будут лежать на одной прямой, что противоречит выпуклости.