Многоугольники, попарно имеющие общую сторону

[provincialka]

Skeptic в сообщении #980403 писал(а):

А этот простейший случай вас устроит?

Меня, например, не устроит. Нет, ну, мед туда складывать удобно. Но к задаче не относится.

-- 20.02.2015, 09:10 --

Некоторые мысли. Предположим, что таких многоугольников не менее 5. Возьмем любой из них. У него есть стороны, общие с хотя бы четырьмя другими, пронумеруем их против часовой стрелки 1, 2, 3, 4. Каждая сторона соответствует одному соседнему многоугольнику.
Рассмотрим многоугольники 1 и 3. каждый лежит в полуплоскости, определяемой прямыми 1 и 3 соответственно (в той, которая не содержит исходный многоугольник). Пусть прямые 1 и 3 пересекаются, например, со стороны ребра 2 (надо уточнить, что это значит). Тогда многоугольник с номером 2 лежит в треугольнике, образованном прямыми 1, 2, 3 и не может иметь общих точек с многоугольником 4.

Хм... как-то так, но надо все изложить более аккуратно.

[ИСН]

"Граф $K_5$ не вкладывается в плоскость" - так пойдёт?

[provincialka]

ИСН
То есть условие выпуклости ни при чем?

[grizzly]

provincialka в сообщении #980405 писал(а):

Пусть прямые 1 и 3 пересекаются, например, со стороны ребра 2 (надо уточнить, что это значит).

А что тут уточнять? Всё так же -- т. пересечения 1 с 3 и наш многоугольник лежат по разные стороны от прямой 2.
И всё в целом, как по мне, достаточно аккуратно.

[ИСН]

provincialka в сообщении #980427 писал(а):

То есть условие выпуклости ни при чем?

Абсолютно.