Отметили все вершины правильного деcятиугольника. Сколько существует незамкнутых несамопересекающихся восьмизвенных ломаных с вершинами в отмеченных точках?

задан 7 Дек '13 12:05

изменен 19 Дек '13 22:49

Deleted's gravatar image


126

1

@serg55: приходится здесь отвечать -- внизу уже места нет. Надеюсь, этот ответ Вы увидите. Задача здесь ставится для незамкнутых ломаных. То есть проблемы с различением замкнутых ломаных тут нет. Их вполне можно было бы рассматривать как фигуры, и так более естественно делать. А можно рассматривать и с отмеченной точкой. Здесь всё зависит от принимаемых соглашений и от постановки задачи. В идеале, любые возможные разночтения должны оговариваться.

(19 Дек '13 1:34) falcao

@falcao: Дословно условия задачи следующие: Отметили все вершины правильного 11-тиугольника. Сколько существует незамкнутых несамопересекающихся девятизвенных ломаных с вершинами в отмеченных точках? Это из 1 тура олимпиады Физтех-2014. Ответом должно быть одно число и тогда возникает вопрос, как понимать условия и что писать в ответе. С уважением.

(19 Дек '13 16:51) serg55
1

@serg55: я сделал "апдейт" того решения, на которое здесь идёт ссылка. Там говорится как раз про 11-угольник и 9-звенные ломаные. Общая формула для $%n$%-угольника там такая: $%n(n-1)2^{n-3}$%. При $%n=11$% это даёт 28160, но это соответствует случаю, когда каждая фигура учитывается дважды (то есть AB...Z -- не то же самое, что Z...BA). И здесь из условия не ясно, какой вариант имеют в виду авторы. Я бы из чисто спортивных соображений положился на случай, когда ломаной считается просто фигура, и ввёл бы на свой страх и риск ответ, поделённый на 2, то есть 14080.

(20 Дек '13 0:08) falcao

@falcao: Огромное спасибо. Рискнем. С уважением.

(20 Дек '13 13:03) serg55
10|600 символов нужно символов осталось
0

Похожая задача разбиралась здесь. Но имеется некоторое отличие, потому что в Вашем случае рассматриваются 8-звенные, а не 9-звенные ломаные. Это обстоятельство можно учесть следующим образом. Для вершин выпуклого $%n$%-угольника, когда все $%n$% вершин задействованы, ответом будет число $%n2^{n-2}$% (например, для треугольника таких ломаных имеется шесть). При этом мы считаем разными две ломаные, вершины которых обходятся в противоположном порядке. Если имеется 10-угольник, а ломаные берутся 8-звенные, то при этом одна из вершин оказывается не задействована. Её выбираем 10 способами, и далее для оставшихся $%n=9$% вершин имеем по формуле $%9\cdot2^7=1152$% ломаных. Ответом будет число $%11520$%.

ссылка

отвечен 7 Дек '13 13:13

@falcao:Я не понял, чем отличаются условия задач: Задача №1: Отметили все вершины правильного 11-тиугольника. Сколько существует незамкнутых несамопересекающихся девятизвенных ломаных с вершинами в отмеченных точках? Задача №2: Отметили все вершины правильного деcятиугольника. Сколько существует незамкнутых несамопересекающихся восьмизвенных ломаных с вершинами в отмеченных точках? По-моему и в том и в другом случаях разница между количеством сторон и количеством звеньев одинаковая, а. т.к. у ломаной вершин на 1 больше чем звеньев, то задачи одинаковые и решаются одинаково, или я неправ?

(18 Дек '13 22:52) serg55

@serg55: спасибо, что обратили внимание на обстоятельство, которое я упустил. Дело в том, что я эту задачу о ломаных встречал когда-то на олимпиаде. И там все точки были задействованы. Когда я давал ответ на задачу по ссылке, то не обратил внимания на то, что там число звеньев на два отстаёт от числа вершин. Слова "девятизвенных" и "десятизвенных" отличаются одной буквой, и я этого не заметил. А здесь обратил внимание, и мне показалось, что задачи отличаются. Хотя они совершенно аналогичные. Здесь всё правильно, а в задаче по ссылке я сделаю "апдейт".

(18 Дек '13 23:22) falcao

@falcao: Если я правильно понял, то в этой задаче результат на два делить не надо, т. к. у нас все варианты разные.

(18 Дек '13 23:47) serg55

@serg55: вопрос о том, надо ли делить на два, не зависит от версии задачи. Он зависит от толкования понятия "ломаная". Если под ним понимать маршрут, где важно, в какой точке он начинается, и в какой кончается, то получится изложенная мной версия. Если же понимать ломаную чисто как геометрическую фигуру (множество точек), то тогда надо дополнительно делить на два. Скажем, при $%n=3$% однозвенных направленных ломаных 6, а фигур (отрезков) всего 3.

(18 Дек '13 23:57) falcao

@falcao: Скажите, а как вы думаете, как надо понимать условие данной задачи? Мне кажется, что требуется указать все сколько существует незамкнутых несамопересекающихся ломаных с вершинами в отмеченных точках, но в тоже время. если совпадают начало и конец ломаных, то это одна ломаная, наверное. Голова идет кругом, очень непонятно.

(19 Дек '13 1:19) serg55
10|600 символов нужно символов осталось
0

В высказанных решениях не понимаю, как учитывается самопересечение, а вернее его отсутствие?

ссылка

отвечен 6 Янв '14 17:37

@Анатолий Бар...: там процесс устроен следующим образом. Одна точка лишняя, её исключаем из рассмотрения (с учётом, что она выбирается $%n$% способами). Дальше выбираем начало ломаной -- оно произвольно. Проводим первый отрезок. Его нельзя проводить как угодно, а можно соединять лишь с соседом. В противном случае диагональ разобьёт всё на две части, и точки без самопересечений будет уже не соединить. Дальше применяется тот же принцип, то есть мы избегаем того, что явно нельзя. А при соединении точек с соседями самопересечений заведомо нет.

(6 Янв '14 18:05) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,035

задан
7 Дек '13 12:05

показан
3384 раза

обновлен
6 Янв '14 18:05

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru