На окружности отмечено 10 точек сколько существует незамкнутых несамопересекающихся девятизвенных

На окружности отмечено 10 точек сколько существует незамкнутых несамопересекающихся девятизвенных

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

Решение

Первую точку можно выбрать десятью способами. Каждую из следующих восьми точек можно выбрать двумя способами: она должна быть соседней с одной из ранее выбранных точек (иначе получится самопересекающаяся ломаная). Поскольку начало и конец при таком подсчёте различаются, а в ломаной – нет, результат нужно разделить на 2. Следовательно, всего имеется 10·2 8 : 2 = 1280 ломаных.

олимпиада — Несамопересекающиеся восьмизвенные ломаные

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

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

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

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

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

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

2 ответа

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

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

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

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

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

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

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

На окружности отмечено 10 точек сколько существует незамкнутых несамопересекающихся девятизвенных

Евгений Пушкин

Решаю Математику, Физику, Химию в любое время!
Быстро и не дорого Всегда онлайн.
———————————————————————
МОЙ VK: https://vk.com/id526536569
ОТЗЫВЫ: https://vk.com/club159102086 ( Математика )

ОТЗЫВЫ https://vk.com/club201952593 ( Физика)

комбинаторика — Ломаные с вершинами в отмеченных точках

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

задан 23 Ноя ’13 22:29

Ответ для @stander (ниже не осталось места для комментариев). Задача про $%n$%-угольник и $%(n-2)$%-звенные ломаные, конечно, сводится к задаче про $%(n-1)$%-угольник и $%(n-2)$%-звенные ломаные (когда все вершины участвуют). У меня об этом написано в Добавлении в явном виде. Сначала мы $%n$% способами выбираем ту вершину, которая не будет участвовать, а потом решаем задачу про $%(n-1)$%-угольник. Вариантов получается в $%n$% раз больше.

2 ответа

Здесь надо вначале условиться о том, считаются ли ломаные вида $%A_1A_2\ldots A_n$% и $%A_n\ldots A_2A_1$% одинаковыми или разными. Если их рассматривать просто как геометрические фигуры, то есть как множества точек, то это одно и то же. В этом же смысле, мы рассматриваем треугольники $%ABC$%, $%ACB$%, $%CAB$% и т.п. как совершенно одинаковые объекты. Тем не менее, я предпочитаю такое толкование, где ломаные с противоположными порядками вершин считаются различными. Это является предметом соглашения, но именно такое понимание удобнее при рассмотрении, скажем, маршрутов. Ясно, что это разные способы: идти от $%A_1$% к $%A_n$% или наоборот.

В случае, если ломаные с противоположным порядком вершин мы отождествляем, полученный далее ответ надо разделить на 2.

Итак, сначала выбираем начальную вершину $%A_1$% ломаной. Это можно сделать $%11$% способами. Следующей вершиной $%A_2$% может быть только соседняя вершина. В противном случае ломаная будет иметь точки самопересечения. Вершина $%A_2$% выбирается двумя способами. Далее выбираем вершину $%A_3$%, что также делается двумя способами: годится любая из вершин, соседняя с $%A_1$% или $%A_2$%, и больше никакая. Далее вершина $%A_4$% снова выбирается двумя способами: предыдущие три вершины идут «плотно» друг за другом, и четвёртая вершина выбирается по соседству с ними с одной из двух сторон. Так всё продолжается, пока мы оказываемся перед выбором последней оставшейся вершины $%A_<11>$%, где способ всего один.

По правилу произведения получается $%11\cdot2^<9>=5632$%, так как выбор из двух вариантов у нас был 9 раз — кроме самого первого и самого последнего шага.

Если ломаные рассматриваются просто как геометрические фигуры, без учёта нумерации вершин, то ответом будет $%2816$%.

Добавление. Сейчас @serg55 обратил моё внимание на то, что здесь была разобрана хотя и похожая, но не совсем та задача. Я на одной из олимпиад встречал задачу о таких ломаных, и там в них были задействованы все вершины. Для случая $%n$%-угольника таких ломаных получается $%n2^$%, если рассматривать ломаные как маршруты. Здесь в условии я по невнимательности принял слово «девятизвенные» за «десятизвенные» и изложил соответствующий вариант. Теперь хочу внести коррективы. Если дан $%n$%-угольник, а ломаные рассматриваются $%(n-2)$%-звенные, то сначала мы $%n$% способами выбираем вершину, которая не будет участвовать, и далее решаем предыдущую задачу для $%(n-1)$%-угольника с $%n-2$% звеньями ломаной. Итогом будет число $%n(n-1)2^$%.