1

Тема: Задача с 5-ого Открытого Кубка

В 5-ом открытом кубке на Гран-При Двух Столиц (ссылка на условия: http://acm.math.spbu.ru/~snark/files/oc … oblems.pdf) предлагалась следующая задача (Problem A на контесте):
Построить из N точек строго выпуклый 4-ехмерный многогранник, у которого любые две вершины соединены ребром, либо определить, что это невозможно. (1<=N<=10)
Кто знает как решать, или решил эту задачу, пожалуйста, поделитесь своими идеями.

2 Отредактировано ScalAr (2009-09-11 10:42:41)

Re: Задача с 5-ого Открытого Кубка

Если я правильно понял задачу, то по моему достаточно взять n точек на 4-мерной сфере, если n>4, а иначе вывести "нет решения"

3 Отредактировано ArtemKadeev (2009-09-11 21:44:22)

Re: Задача с 5-ого Открытого Кубка

А если я конечно эту задачу понял верно, то ответ существует только для 5.
Иначе какие то две вершины не будут соединены ребром.
Ну в двумерном например все понятно - там можно построить только треугольник, при добавлении еще одной вершины количество ребер увеличится на 2, а не на три, что требуется.
В трехмерном для Тетраэдра(вроде так он называется) тоже все очевидно.

Можно даже попробовать это доказать фактически для n-мерного.(на примере 4-х)

Возьмем 4-мерное пространство.
Докажем, что построение |V|<5 невозможно. Для этого берем одну вершину, от нее идет максимум три ребра.
Фигура, создаваемая этими ребрами вырождена в 4-мерном пространстве, поскольку для создания базиса надо 4 вектора хотя бы.(Т.е. можно упростить эту фигурку до 3-х мерного пр-ва)
Для 5 у нас решение есть...
Теперь докажем, что построить для |V|>5 также невозможно. Добавим к пятиугольнику еще одну вершину, тогда из нее будет выходить 5 ребер, и все они должны быть внешние. Но мы знаем, что 5 ребер не могут быть линейно независимые в 4-х мерном пр-ве => одно какое-то может быть представлено через другие 4. Тогда одно из ребер будет находиться внутри фигуры, и не являться необходимым для построения фигуры => условие про соединенность ребрами нарушается, поскольку его можно удалить.
Не очень аккуратно математически, но вполне логичное доказательство.

В итоге ответ существует только при n=5, и он нам дан в условии)

4

Re: Задача с 5-ого Открытого Кубка

ArtemKadeev пишет:

А если я конечно эту задачу понял верно, то ответ существует только для 5.

Это неправильная идея. Я первый сабмит сделал именно таким образом smile Итог - WA.

По поводу идеи со сферой ничего не могу сказать о правильности. Надо будет попробовать закодить, хотя там мне не все понятно.

Есть ли у кого-то еще идеи?

5

Re: Задача с 5-ого Открытого Кубка

мы знаем, что 5 ребер не могут быть линейно независимые в 4-х мерном пр-ве => одно какое-то может быть представлено через другие 4. Тогда одно из ребер будет находиться внутри фигуры, и не являться необходимым для построения фигуры

Неверно. Из линейной независимости не следует что ребро обязательно лежит внутри. И вообще, следуя этим рассуждениям, можно получить, что в 3-мерном пространстве существуют только 4-вершинные выпуклые многогранники smile

6 Отредактировано ArtemKadeev (2009-09-12 18:47:51)

Re: Задача с 5-ого Открытого Кубка

ScalAr пишет:

Неверно. Из линейной независимости не следует что ребро обязательно лежит внутри. И вообще, следуя этим рассуждениям, можно получить, что в 3-мерном пространстве существуют только 4-вершинные выпуклые многогранники smile

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

7

Re: Задача с 5-ого Открытого Кубка

Ответ существует для любого n > 4. На разборе рассказывалось решение, в котором несколько раз кидались случайные точки на сферу, а потом делалась проверка. Проверка -- самая сложная часть.

8

Re: Задача с 5-ого Открытого Кубка

Мне рассказывали сдавшие её тогда люди, что в качестве ответа подходит что то вроде (t,t^2,t^3,t^4) для различных t. И что это всё следует из какой-то глубокой теории, которая им была известна. Сомневаюсь, что кто-то решал эту задачу так, как предлагалось на разборе wink

9 Отредактировано ScalAr (2009-09-15 15:49:34)

Re: Задача с 5-ого Открытого Кубка

shtserg пишет:

Мне рассказывали сдавшие её тогда люди, что в качестве ответа подходит что то вроде (t,t^2,t^3,t^4) для различных t. И что это всё следует из какой-то глубокой теории, которая им была известна. Сомневаюсь, что кто-то решал эту задачу так, как предлагалось на разборе

Да, тоже верное решение. Это следует из того, что определитель Вандермонда никогда не равен нулю. В принципе, если догадаться, что никакие 5 точек не должны лежать в одном 3-х мерном пространстве, то такое решение становится почти очевидным. а насчет сферы- по моему можно обойтись без проверки, ведь вероятность, что из случайно сгенерированных 10 точек какие либо 5 лежат в одном пространстве крайне мала.

10

Re: Задача с 5-ого Открытого Кубка

Спасибо всем за идеи.

11

Re: Задача с 5-ого Открытого Кубка

Решал и я ту задачу... Честно признаюсь, ни тогда, ни сейчас я не понимаю, что такое выпуклая фигура в 4-мерном пр-ве, у которой все вершины соединены со всеми ))) Насколько я знаю, все её решали одинаково: random + проверка, подходит нам этот многогранник или нет.