|
Отметили все вершины правильного 11-тиугольника. Сколько существует незамкнутых несамопересекающихся девятизвенных ломаных с вершинами в отмеченных точках? задан 23 Ноя '13 22:29 
Амелия_TO |
|
Здесь надо вначале условиться о том, считаются ли ломаные вида $%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-2}$%, если рассматривать ломаные как маршруты. Здесь в условии я по невнимательности принял слово "девятизвенные" за "десятизвенные" и изложил соответствующий вариант. Теперь хочу внести коррективы. Если дан $%n$%-угольник, а ломаные рассматриваются $%(n-2)$%-звенные, то сначала мы $%n$% способами выбираем вершину, которая не будет участвовать, и далее решаем предыдущую задачу для $%(n-1)$%-угольника с $%n-2$% звеньями ломаной. Итогом будет число $%n(n-1)2^{n-3}$%. отвечен 23 Ноя '13 23:52 
falcao @IvanLife: какой Вы видите смысл в сверке ответов, получаемых подстановкой чисел в готовые формулы? Ведь я умею перемножать числа нисколько не лучше, чем Вы. Одно дело -- обсуждать какие-то тонкости или неочевидные моменты решения, и другое -- выполнять чисто "механическую" работу.
(5 Янв '14 11:11)
falcao
@falcao, я хотел обратить ваше внимание на то, что мой ответ в 10 раз больше вашего (в случае когда вы рассматривали ломаные как геометрические фигуры)
(5 Янв '14 14:27)
IvanLife
@IvanLife: меня часто в последнее время "донимали" сверкой ответов в ситуациях совершенно "диких". Типа того, что есть последовательность чисел, где ответом является 12-е число. У кого-то другая версия задачи, и там получается 10-е по счёту. Идёт вопрос: а там ответ на самом деле 10? Это я до десяти должен сосчитать! Таких случаев было уже очень много, и я начал "обострённо" на это всё реагировать. Вашего замечания я не воспринял по причине того, что у меня в Добавлении приведена общая формула и написано ровно то же самое, что и у Вас. Просто поначалу я излагал решение не той задачи.
(5 Янв '14 14:40)
falcao
@stander: здесь фактически не одна задача, а целых четыре. В том смысле, что можно использовать все вершины или все вершины кроме одной, считая их пронумерованными или нет. Вы рассматриваете вариант со всеми $%n$% вершинами и приходите к ответу $%n2^{n-2}$% (у меня было $%11\cdot2^9=5632$%), если $%A_1...A_n$% и $%A_n...A_1$% считаются разными, а потом дополнительно делите на 2, если мы принимаем соглашение, что это одно и то же. Но я говорю о том же самом, и привожу число $%2816$% как ответ для такого случая. То есть ответы совпадают.
(7 Янв '14 5:53)
falcao
@stander: у меня в конце Добавления приведена такая же формула, но с показателем степени $%n-3$%, потому что она относиться к случаю, где ещё не было произведено деление пополам. Там же всё явно написано -- к какой версии относится этот ответ. Если под ломаными понимается геометрическая фигура, и порядок прохождения звеньев не важен, то ответ должен быть в два раза меньше, о чём также было написано.
(7 Янв '14 15:09)
falcao
если в задаче n-2 ломанных (в моем случае 9) то просто надо n вставить в эту формулу n(n−1)2n−3 и мы получим ответ?
(15 Янв '14 21:33)
HULK29
@denisivlev989: я Вам рекомендовал бы понять идею решения, то есть усвоить сам метод и применить его к Вашему случаю. Низведение математики до "аппарата" и подстановки чисел в формулы, в отрыве от смысла, я очень не приветствую.
(15 Янв '14 21:41)
falcao
а вот если нам надо найти ломанные как геометрические фигуры, то получается полученный в этой формуле n(n−1)2n−3 результат нам надо разделить на 2 или нет ?
(17 Янв '14 15:48)
HULK29
@denisivlev989: я Вам советую решить задачу как бы "с нуля", проделав все необходимые действия. Это совсем не трудно, так как образец решения имеется. Это было бы во много раз полезнее "механической" подстановки чисел в формулы, с выяснением того, а что же по этой формуле было вычислено. Считать при этом удобно сначала число ломаных как маршрутов, а в самом конце делить на 2, получая число ломаных как фигур.
(17 Янв '14 17:07)
falcao
я не пойму как мы n способами выбираем вершину, которая не будет участвовать
(17 Янв '14 17:51)
HULK29
@denisivlev989: вот такие вопросы по решению я всячески приветствую и готов на них отвечать. В данном случае речь идёт о некой очевидности. Есть n различных предметов; сколькими способами из них можно выбрать один? Ответ: n способами. Здесь ровно то же самое. Смысл в том, что мы знаем, сколько вершин должно войти в ломаную: она не замкнута, звеньев 9, поэтому вершин 10. Одна вершина не будет участвовать. Это может быть любая из 11 вершин. Пока что-то по решению не ясно, я охотно готов эти моменты обсуждать.
(17 Янв '14 18:28)
falcao
т.е получается мы имеем 10 вершин, выбрать начальную вершину ломаной можно 10 способами. Следующей вершиной A2 может быть только соседняя вершина.ВершинаA2выбирается двумя способами. Далее выбираем вершину A3, что также делается двумя способами. Далее вершина A4 снова выбирается двумя способами.Так всё продолжается, пока мы оказываемся перед выбором последней оставшейся вершины A10, где способ всего один. По правилу произведения получается 10⋅2 в восьмой степени=2560, так как выбор из двух вариантов у нас был 8 раз-кроме самого первого и последнего шага. праильно ли я понял принцип решения?
(17 Янв '14 19:08)
HULK29
@denisivlev989: какой из вариантов задачи Вы сейчас рассматривали? Сколько должно быть вершин, и сколько звеньев? У меня первоначально была рассмотрена не та задача, которая дана в условии, а в Добавлении я уже рассмотрел тот вариант, который имелся в виду.
(17 Янв '14 19:22)
falcao
Отметили все вершины правильного 11-тиугольника. Сколько существует незамкнутых несамопересекающихся девятизвенных ломаных с вершинами в отмеченных точках?,т.е мы правильно выбрали возможную вершину десятью способами или нет ?
(17 Янв '14 19:24)
HULK29
@denisivlev989: нет, потому что при такой постановке задачи мы сначала 11 способами выбираем то, что не будет участвовать. Уже потом начинаем строить ломаную, и 10 способами выбираем начальную вершину. А после этого начинаем домножать на двойки.
(17 Янв '14 19:43)
falcao
т.е для 11угольника и девятизвенной ломанной,10 способами выбираем начальную вершину,домножаем до 2 в восьмой степени,т.к. кроме первой и последней вершины и получаем 10*28=2560. сейчас верная последовательность решения или нет?я никак не пойму
(17 Янв '14 19:46)
HULK29
показано 5 из 17
показать еще 12
|
|
можете написать ответ для 11угольниа и 9звенной ломанной и объяснить решение данной задачи отвечен 18 Янв '14 14:29 
HULK29 @denisivlev989: решение я уже объяснил многократно. Выписывание ответа, если Вы поняли принцип решения, не должно вызывать проблем. По поводу того, что Вы писали выше: у меня ведь было сказано, что сначала надо умножить на 11, потом на 10, и потом на несколько двоек. У Вас множитель 11 почему-то исчез.
(18 Янв '14 14:53)
falcao
а это мы найдем ломанные как маршруты или нет ?
(18 Янв '14 15:22)
HULK29
@denisivlev989: а Вы сами как считате? И нет ли у Вас ощущения, что мы уже долго топчемся на одном месте, переспрашивая одно и то же? Я считаю, что информация дана более чем исчерпывающая. Не вижу здесь никакой "почвы" для дальнейших обсуждений.
(18 Янв '14 19:25)
falcao
|
Ответ для @stander (ниже не осталось места для комментариев). Задача про $%n$%-угольник и $%(n-2)$%-звенные ломаные, конечно, сводится к задаче про $%(n-1)$%-угольник и $%(n-2)$%-звенные ломаные (когда все вершины участвуют). У меня об этом написано в Добавлении в явном виде. Сначала мы $%n$% способами выбираем ту вершину, которая не будет участвовать, а потом решаем задачу про $%(n-1)$%-угольник. Вариантов получается в $%n$% раз больше.