Задача 58313

Темы:    [ Правило произведения ] [ Системы точек и отрезков (прочее) ]

Сложность: 3 Классы: 8,9

Условие

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

Решение

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

Ответ

1280 ломаных.

Источники и прецеденты использования

книга
Автор	Прасолов В.В.
Год издания	2001
Название	Задачи по планиметрии
Издательство	МЦНМО
Издание	4*
глава
Номер	27
Название	Индукция и комбинаторика
Тема	Неопределено
параграф
Номер	2
Название	Комбинаторика
Тема	Комбинаторика (прочее)
задача
Номер	27.007