Допустим, у нас есть много правильных N-угольников. Вася берет первый из них, раскрашивает. Остальные многоугольники он прикладывает друг другу так, чтобы
1) Они сошлись сторонами
2) Они не пересекались
Задача: минимальным кол-вом многоугольников вымостить путь от первого многоугольника к первому.
На рисунке представлены размещение для N=3,4,5,6,7,8.
Задача: указать формулу для определения этого числа, если формулы не существует - тогда указать асимптотику или эффективный алгоритм перебора )
Решения задачи не знаю (
1) Они сошлись сторонами
2) Они не пересекались
Задача: минимальным кол-вом многоугольников вымостить путь от первого многоугольника к первому.
На рисунке представлены размещение для N=3,4,5,6,7,8.
Задача: указать формулу для определения этого числа, если формулы не существует - тогда указать асимптотику или эффективный алгоритм перебора )
Решения задачи не знаю (
-
-
14.06.2008 в 19:06может их можно разместить компактнее?
например вот так:
заранее извиняюсь за плохой рисунок))
-
-
14.06.2008 в 19:12У тебя точно неправильно: ведь в таком случае углы в центре должны быть 90 градусов, а у нас пятиугольник.
-
-
14.06.2008 в 20:17А как вариант нащет пяти, которые сходяться в центре?
-
-
14.06.2008 в 20:40n-угольники будут сходиться в центре (если я правильно понимаю смысл твоего слова сходиться), если 360 нацело делится на величину угла при вершине n-угольника
Угол при вершине правильного n- угольника равен 180(n-2)/n
360 делится на 180(n-2)/n нацело, если 2n/(n-2) - целое число
При n=5 10/3 не является целым
-
-
14.06.2008 в 21:33Или я ошибся. (или не понял условия =)
И, да:
-
-
14.06.2008 в 21:40-
-
15.06.2008 в 21:56Два вопроса не в тему:
1) Зачем Вася их раскрашивает? Мне сразу на ум пришла совсем другая задача о раскрашивании... Тут вроде это не актуально?
2) Можно ли доказать, что для любого количества углов такое построение возможно?
-
-
15.06.2008 в 22:072) Понятия не имею
Вообще комбинация "3 в одну сторону, три в другую сторону", работает для проверенных N=3..8. Может быть она и для любого N работает, не было времени проверить и доказать.
Но когда появится время, я проверю (если никто не проверит).
-
-
15.06.2008 в 22:31Мне всю ночь многоугольники снились. Все подсчитывала величины углов, находила какие-то целые части, момент поворота.. Ужас!
Смыкание в центре будет только для n=3,4,6
И аналитически получается, что для n=5,8,12 (еще и 6) внутри образуется правильный m-угольник (соответственно m=12 или 10(не помню точно, но это больше, чем на рисунке),4,3)
То есть получается, что вроде с 12-угольниками можно вымостить так, что их всего понадобится 3. Но я не рисовала
-
-
15.06.2008 в 22:43А мне - вирусы, которые ломают жесткий диск. А там - незаконченный диплом про эти самые вирусы
-
-
15.06.2008 в 22:46Сохраняй еще на флешку (кстати, ты ее нашел?)
Amicus Plato
С возвращением!
-
-
16.06.2008 в 01:30Поэтому для любого 4m-угольника хватит четырех, для 6m-угольника — трех.
И нужно для произвольного p-угольника (p - простое) доказать, что 6 хватит (до 19 проверил - надоело).
Идея примерно такая - берется 3 p-угольника, у первого из них выбирается одна из его сторон. Остальные два к нему стыкуются так, чтобы одна из сторон третьего p-угольника была параллельна выбранной, и вместе с выбранной стороной лежала по одну сторону от прямой, соединяющей центры второго и третьего p-угольников. Т.е., получится такая дуга. И к ней прицепляется такая же дуга, но перевернутая.
Выглядит это так:
Ну, доказательство существования такой дуги полуграфическое. Для любого правильного p-угольника (любое простое число, большее двух - нечетное) существует ось симметрии, проходящая через одну вершину и центр описанной окружности (на рисунке - розовая линия для зеленого 11-угольника). Перпендикуляр к этой оси симметрии, проведенный к центру описанной окружности, пересекает две стороны p-угольника. К этим сторонам цепляются еще два p-угольника, причем симметрично (p ≠ 5, там получается немного по-другому). Тогда по одной стороне первого и третьего (синего и красного) p-угольников будут лежать на одной прямой, отсекающей полуплоскость, содержащую все три p-угольника. ∎ (здесь еще нужно показать, что прицепленные вот так многоугольники не будут пересекаться - но мне лень доказывать почти очевидное).
Дальше к этой дуге подгоняется отраженная (серая).
А вот теперь я думаю. А как доказать, что меньше нельзя?) И доказать, что, например, 256-угольников понадобится минимум 4...
-
-
16.06.2008 в 14:41Какая красивая мысль!!
Перпендикуляр к этой оси симметрии, проведенный к центру описанной окружности, пересекает две стороны p-угольника
А вот это точно? Через две вершины не может пройти? (если вопрос тупой, прошу не бить)
до 19 проверил - надоело)
Ну, у тебя и терпение..
-
-
16.06.2008 в 15:03С возвращением!
Спасибо! )))
Adjirranirr
Здорово! Просто вообще словами не передать!
Sensile А вот это точно? Через две вершины не может пройти? (если вопрос тупой, прошу не бить)
Для нечетного количества углов, по идее, вообще нельзя как ни старайся провести через центр прямую, которая пройдет через две вершины одновременно.
А поскольку у нас прямая перпендикулярна оси симметрии, то никак иначе, как пересечь две стороны, она пройти не может.
---
Меня особенно восхищает вот это:
Тогда по одной стороне первого и третьего (синего и красного) p-угольников будут лежать на одной прямой, отсекающей полуплоскость, содержащую все три p-угольника.
Да-а! Красиво!
А как доказать, что меньше нельзя?) И доказать, что, например, 256-угольников понадобится минимум 4...
Ну.... Два не может быть по определению.
Для трех возможны варианты: либо они смыкаются вершинами, либо у них внутри правильный треугольник.
Смыкаются вершинами три шестиугольника. Они нам не подходят.
А правильный треугольник образуют 12-угольники, если я не ошибаюсь.
Может, конечно, возможны более экзотические ситуации...
(Меня тоже, если чего, не бить)))
-
-
16.06.2008 в 15:23Как раз из рассуждений про k·m-угольники получается, что тройки дают только 6k-угольники.
-
-
16.06.2008 в 15:33С интересом прочитал
-
-
16.06.2008 в 15:46Из этих рассуждений следует, что для 6k-угольников хватит трех. Но может быть трех хватит не только для 6k-угольников.
-
-
16.06.2008 в 15:58По-моему, тут в обе стороны должно действовать...
То есть есть некоторое порождающее количество многоугольников, задаваемое простым числом вершин (3, 4, 6), и улучшить его, кратно увеличивая вершины, невозможно.
Думаю, это можно доказать. Хотя... Не знаю...
-
-
16.06.2008 в 18:22Если три m-угольника можно составить, что выглядеть это будет так:
Три продолжения сторон сходятся в одной точке, являющейся центром окружностей, описанных вокруг фигур, намеченных пунктирными линиями (так как p-угольники правильные, то больший пунктирный треугольник тоже правильный; а так же равны многоугольники, отрезанные пунктиром от каждого из p-угольников (в данном случае это трапеции); значит, бирюзовые линии являются биссектрисами углов правильного треугольника и сходятся в одной точке. □
Следовательно, p-угольники можно составить тройкой тогда и только тогда, когда хотя бы один из таких углов равен 120°:
Рассмотрим такой угол:
Число p - простое; следовательно, число 360°/p - не целое.
Угол p-угольника равен 180°·(p - 2)/p; дополняющий его до 360° = 360° - 180° + 360°/p = 180°·(1 + 2/p).
Сумма всех углов невыпуклого многоугольника должна быть целой; тогда,
(2·360°/p + 180°·(1 + 2/p)·k + α
2·360°/p + 180°·(1 + 2/p)·k + α = 720/p + 180p·k/p + 360·k/p + α = (720 + 360·k + 180p·k)/p + α = 180(4 + 2k + p·k))/p + α.
Если α - целое, то
180·(4 + 2k + p·k)) ≡ 0 mod p <=> 180·(4 + 2k) ≡ 0 mod p <=> 180 ≡ 0 mod p ∨ 2 + k ≡ 0 mod p.
Так как 180 ≢ 0 mod p,
2 + k ≡ 0 mod p.
Но k < p/2 - 2 ∧ p ≥ 5 ∧ p - простое => 2 + k ≢ 0 mod p. Значит,
180·(4 + 2k) ≢ 0 mod p => α ∉ Z => α ≠ 120° □
И из этого так же следует, что α ≠ 90°, и для любого простого p выстроить и тремя и четырьмя фигурками не получится.
Осталось доказать для пяти=)
-
-
16.06.2008 в 19:38Высокий класс!
Именно это я и мела в виду (это я про первую часть с правильным треугольником), но только в виде смутных мыслей.
Всё, что дальше, я б наверное ни в жизнь не формализовала...
Но разве там всё ограничивается треугольником внутри?
Это можно обобщить на случай невыпуклого n-угольника?
-
-
16.06.2008 в 20:42А треугольник внутри вообще непричем. Нас интересует треугольник, который у меня показан пунктиром. А он всегда треугольник, и всегда правильный.
Или я не так понял вопрос?)
-
-
16.06.2008 в 21:14ну, да...
это я уже немножко не в ту степь.
Я не про простое р.
А вот приблизительно о чем. Как-то это должно легко доказываться... Точно так же, похоже. А может даже гораздо проще.
Вот, предположим для многоугольников с количеством вершин, кратных 6.
6-ти и 12-угольники.
24-угольник будет уже иметь вот такой стык:
(это самая его середина).
В принципе, для достаточно большого количества углов, например, 256, кто мешает так соединиться не только многоугольникам, полученным из шестиугольников?
Но однако это сделать нельзя (как мне кажется) и доказывается это как-то похоже.
А вот кстати!
Любой k·m-угольник можно получить "отрезанием" некоторых кусков от k-угольника; поэтому, если k-угольники можно сложить, и их минимум будет, скажем, x, то этого минимума хватит и для k·m-угольника.
Кажется, посылка не верна!
m не любое, а только степени двойки!
18-угольник (правильный, конечно) из 6-угольника не получишь.
-
-
16.06.2008 в 21:23Мне сначала тоже так показалось, но...
i041.radikal.ru/0806/b4/75f429b1ede1.png
-
-
16.06.2008 в 21:37Пардон...
Да уж...
Беру все свои слова назад!
-
-
16.06.2008 в 23:27Меня тоже сначала это место смутило))