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

[VVV]

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

[Лев]

d+1 ? 

[VVV]

d+1 ? 

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

[iPhonograph]

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

[Лев]

Не меньше? 

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

[VVV]

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

  Это правда.

[iPhonograph]

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

[VVV]

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

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

[zhekas]

Ну коль 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 точек образуют выпуклую оболочку. Либо внутри этой оболочки либо на её границе (на сторонах кроме вершин) обязательно найдётся точка из целочисленной решётки. Вот именно она и будет общей для всех подмножеств

[VVV]

Ну коль 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 точек образуют выпуклую оболочку. Либо внутри этой оболочки либо на её границе (на сторонах кроме вершин) обязательно найдётся точка из целочисленной решётки. Вот именно она и будет общей для всех подмножеств

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

[zhekas]

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

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

[iPhonograph]

Выберем 5 таких точек M1 M2 M3 M4 M5. Эти 5 точек образуют выпуклую оболочку. Либо внутри этой оболочки либо на её границе (на сторонах кроме вершин) обязательно найдётся точка из целочисленной решётки. Вот именно она и будет общей для всех подмножеств

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

[VVV]

Выберем 5 таких точек M1 M2 M3 M4 M5. Эти 5 точек образуют выпуклую оболочку. Либо внутри этой оболочки либо на её границе (на сторонах кроме вершин) обязательно найдётся точка из целочисленной решётки. Вот именно она и будет общей для всех подмножеств

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

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

[iPhonograph]

[Лев]

Выберем 5 таких точек M1 M2 M3 M4 M5. Эти 5 точек образуют выпуклую оболочку. Либо внутри этой оболочки либо на её границе (на сторонах кроме вершин) обязательно найдётся точка из целочисленной решётки. Вот именно она и будет общей для всех подмножеств

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