Номер 3, страница 392, часть 1 - гдз по алгебре 10-11 класс задачник Мордкович, Семенов

Темы исследовательских работ к главе 9. ч. 1 - номер 3, страница 392.

3. Симметричные и несимметричные деревья вариантов.

Дерево вариантов — это наглядная схема, которая помогает перечислить и подсчитать все возможные исходы (варианты) какого-либо действия или эксперимента, состоящего из нескольких последовательных шагов. Корень дерева представляет начало процесса, ветви — возможные действия на каждом шаге, а листья (конечные вершины) — итоговые результаты. В зависимости от условий задачи, деревья вариантов могут быть симметричными и несимметричными.

Симметричные деревья вариантов

Дерево вариантов называется симметричным, если на каждом шаге (уровне дерева) из любой вершины выходит одинаковое количество ветвей. Это означает, что количество вариантов выбора на текущем шаге не зависит от того, какие именно решения были приняты на предыдущих шагах.

Пример: Сколько различных четырехзначных пин-кодов можно составить, используя цифры от 0 до 9?

Процесс состоит из четырех последовательных шагов — выбора каждой из четырех цифр пин-кода.

• Шаг 1: Для первой цифры есть 10 вариантов (любая цифра от 0 до 9).
• Шаг 2: Для второй цифры также есть 10 вариантов, так как цифры могут повторяться. Этот выбор не зависит от первой цифры.
• Шаг 3: Для третьей цифры снова 10 вариантов.
• Шаг 4: Для четвертой цифры — 10 вариантов.

В таком дереве из корневой вершины выйдет 10 ветвей. Из каждой из 10 полученных вершин выйдет еще по 10 ветвей, и так будет продолжаться на всех четырех уровнях. Общее количество вариантов подсчитывается по правилу умножения в комбинаторике. Если процесс состоит из $k$ шагов и на каждом шаге доступно $n$ вариантов, то общее число исходов равно $n^k$.

Для нашего примера $k=4$ и $n=10$. Общее количество пин-кодов: $10 \times 10 \times 10 \times 10 = 10^4 = 10000$.

Ответ: В симметричном дереве вариантов количество выборов на каждом этапе постоянно. Общее число исходов ($N$) находится как произведение числа вариантов на каждом шаге, что для одинакового числа вариантов ($n$) на $k$ шагах сводится к формуле $N = n^k$.

Несимметричные деревья вариантов

Дерево вариантов называется несимметричным, если количество ветвей, исходящих из вершин одного и того же уровня, может быть разным. Такая ситуация возникает, когда количество доступных вариантов на очередном шаге зависит от конкретного выбора, сделанного на предыдущем шаге.

Пример 1 (убывающее число вариантов): В забеге участвуют 5 спортсменов. Сколькими способами могут распределиться три призовых места (золото, серебро, бронза)?

• Шаг 1 (Золото): На первое место претендуют 5 спортсменов. 5 вариантов.
• Шаг 2 (Серебро): После того как один спортсмен получил золото, на второе место претендуют оставшиеся 4. Из каждой из 5 вершин первого уровня будет выходить по 4 ветви.
• Шаг 3 (Бронза): После распределения первых двух мест на третье претендуют оставшиеся 3 спортсмена. Из каждой вершины второго уровня будет выходить по 3 ветви.

Хотя из всех вершин одного уровня выходит одинаковое количество ветвей ($5 \to 4 \to 3$), само дерево не является строго симметричным, так как количество ветвей меняется от уровня к уровню. Общее число способов: $5 \times 4 \times 3 = 60$.

Пример 2 (явная асимметрия): Турист хочет посетить два города из трех: Рим, Париж, Лондон. Но он не хочет ехать в Лондон сразу после Парижа. Сколько у него вариантов маршрута?

Строим дерево вариантов:

• Корень (выбор первого города):
  • Ветвь "Рим": после него можно поехать в Париж или Лондон. (2 варианта)
  • Ветвь "Париж": после него можно поехать только в Рим (в Лондон нельзя по условию). (1 вариант)
  • Ветвь "Лондон": после него можно поехать в Рим или Париж. (2 варианта)

Вершины "Рим", "Париж" и "Лондон" находятся на одном уровне (первый шаг), но из них выходит разное количество ветвей (2, 1 и 2 соответственно). Это делает дерево несимметричным. Для подсчета общего числа вариантов нужно сложить количество конечных исходов по каждой из начальных ветвей: $2 + 1 + 2 = 5$.

Ответ: В несимметричном дереве вариантов количество выборов на каком-либо шаге зависит от ранее принятых решений. Общее число исходов находится либо путем перемножения числа вариантов на каждом шаге, если оно меняется только от уровня к уровню, либо путем сложения итоговых вариантов по каждой из различающихся ветвей.