а) Какое наименьшее число звезд должно быть на небе, чтобы из любой точки Земли можно было увидеть хотя бы две звезды? Более формально: какое наименьшее число точек нужно разместить на сфере, чтобы любая открытая полусфера содержала не меньше 2 точек? (*для замкнутых полусфер ответ очевиден)
б) Какое наименьшее число звезд должно быть на небе, чтобы из любой точки Земли можно было увидеть хотя бы k звезд?
в) Тот же вопрос для сферы произвольной размерности d.
Решение.
ОтветитьУдалитьТеорема Гейла утверждает, что наименьшее число звезд на небе, удовлетворяющее условиям, равно 2k+d. Очевидна оценка >=2k+d, так как в d-мерной сфере можно провести экваториальную (d-1)-сферу через d точек, а в оставшихся двух открытых полусферах по условию в каждой >=k точек. Доказательство равенства хитрее. Сам Гейл использовал для этого изобретенное им понятие двойственности Гейла. При помощи этой двойственности можно переформулировать задачу так: в пространстве размерности n существует симплициальный многогранник с любым числом вершин (большим n), у которого любые целая_часть(n/2) вершин образуют грань. Такие многогранники называются смежностными, и известно, что они существуют (есть явная конструкция, так называемый циклический многогранник). Вообще, двойственность Гейла --- очень крутая штука. Она позволяет сводить всякие многомерные задачи о многогранниках к простым маломерным моделям. Например, с помощью нее строится выпуклый многогранник, который невозможно построить с рациональными координатами вершин. Двойственность Гейла нормально и четко изложена в Grunbaum "Convex polytopes". Про смежностные многогранники можно прочитать там же, или в Ziegler "Lectures on polytopes" (ее недавно перевели на русский, но про двойственность Гейла там ни хрена не понятно).