Форум умных людей

   Для целочисленной решетки Z^d (d=2,3) найдите такое наименьшее число k(d), что верно следующее утверждение.  Для любого  конечного семейства выпуклых подмножеств  Z^d, такого что пересечение любых k(d) из них непусто, следует, что пересечение всех подмножеств из этого семейства непусто. Множество S из Z^d назывется выпуклым, если существует  такое выпуклое множество T из R^d, что S является пересечением T и Z^d.

d+1 ?  :pinkgirl:

  Приведите, пожалуйста, обоснования этого утверждения.

к(2) не меньше 4

Не меньше?  :roll:

Я пытаюсь доказать в сторону "Не больше". Или я неправильно понял условие?

  Это правда.

правильный ответ, наверное, 2^d

  И это тоже правда. Осталось это доказать.

Ну коль 2^d Попробуем доказать что при d=2 будет k(2)=4. Путь количество подмножеств равно n
Для n=4 доказывать ничего не надо.
Пусть доказано для n=k-1. Докажем для n=k. Методом от противного. Итак у нас есть подмножества A1, A2, A3, ..., Ak. Пусть у нас любые k-1 подмножеств имеют общую точку а k нет. Это означает, что для любого подмножества Ai существует точка Mi, что что Mi принадлежит всем подножествам кроме Ai.
Выберем 5 таких точек M1 M2 M3 M4 M5. Эти 5 точек образуют выпуклую оболочку. Либо внутри этой оболочки либо на её границе (на сторонах кроме вершин) обязательно найдётся точка из целочисленной решётки. Вот именно она и будет общей для всех подмножеств

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

Всё сводится к доказательству, что произвольный выпуклый пятиугольник, вершины которого целые точки, содержит внутри себя целую точку

Ну а если эта точка, например, очень близка к точке М1 и не входит в А1, что тогда?

  Да, это я слишком поторопился. Не любая точка подойдет.

(http://img713.imageshack.us/img713/7704/28661757.png)

Вот этот момент можно подробней?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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