Решение задачи: Красим решающее дерево

Вот решение задачи, оформленное так, чтобы школьнику было удобно переписать в тетрадь:

Задача: Красим решающее дерево

На доске нарисовали полное бинарное решающее дерево глубины 3, классифицирующее точки \((x, y, z)\). У дерева 15 вершин: в 8 листьях записаны классы, а во всех 7 внутренних вершинах — линейные условия на одну из переменных (например, \(y < -2\)).

Кто-то стёр все листья, а в каждой внутренней вершине оставил только название переменной, участвовавшей в условии (\(x\), \(y\) или \(z\)). После стирания выполнено требование: в каждой паре соединённых вершин «предок — потомок» переменные различаются.

Два результата стирания считаются различными, если существует хотя бы одна внутренняя вершина, содержащая различные переменные. При этом форма дерева и подписи да/нет на рёбрах зафиксированы.

Сколько различных деревьев (с точки зрения подписанных во внутренних вершинах переменных) могло остаться после стирания?

Решение:

Давайте разберем условия задачи и структуру дерева.

1. Структура дерева:

• Полное бинарное дерево глубины 3.
• Количество внутренних вершин: \(2^3 - 1 = 7\).
• Количество листьев: \(2^3 = 8\).

Внутренние вершины расположены на уровнях 0, 1, 2.

• Уровень 0: 1 вершина (корень)
• Уровень 1: 2 вершины
• Уровень 2: 4 вершины

Всего 7 внутренних вершин.

2. Переменные:

• В каждой внутренней вершине записывается одна из переменных: \(x, y, z\).

3. Ограничение:

• В каждой паре соединённых вершин «предок — потомок» переменные различаются.

Нам нужно найти количество способов расставить переменные \(x, y, z\) в 7 внутренних вершинах так, чтобы выполнялось это ограничение.

Давайте обозначим переменные в вершинах как \(V_0\) (корень), \(V_{1L}, V_{1R}\) (потомки корня), \(V_{2LL}, V_{2LR}, V_{2RL}, V_{2RR}\) (потомки вершин уровня 1).

Рассмотрим расстановку переменных по уровням:

Уровень 0 (Корень):

• Для корня \(V_0\) мы можем выбрать любую из 3 переменных (\(x, y, z\)).
• Количество вариантов для \(V_0\): 3.

Уровень 1 (Потомки корня):

• Для каждой вершины уровня 1 (например, \(V_{1L}\)) её переменная должна отличаться от переменной её предка \(V_0\).
• Если \(V_0\) выбрана, то для \(V_{1L}\) остаётся 2 варианта переменных.
• Аналогично, для \(V_{1R}\) остаётся 2 варианта переменных.
• Количество вариантов для \(V_{1L}\): 2.
• Количество вариантов для \(V_{1R}\): 2.

Уровень 2 (Потомки вершин уровня 1):

• Для каждой вершины уровня 2 (например, \(V_{2LL}\)) её переменная должна отличаться от переменной её предка \(V_{1L}\).
• Если \(V_{1L}\) выбрана, то для \(V_{2LL}\) остаётся 2 варианта переменных.
• Аналогично для \(V_{2LR}\), \(V_{2RL}\), \(V_{2RR}\).
• Количество вариантов для каждой из 4 вершин уровня 2: 2.

Общее количество вариантов:

Перемножим количество вариантов для каждой вершины:

\[ \text{Общее количество вариантов} = (\text{Варианты для } V_0) \times (\text{Варианты для } V_{1L}) \times (\text{Варианты для } V_{1R}) \times (\text{Варианты для } V_{2LL}) \times (\text{Варианты для } V_{2LR}) \times (\text{Варианты для } V_{2RL}) \times (\text{Варианты для } V_{2RR}) \] \[ \text{Общее количество вариантов} = 3 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \] \[ \text{Общее количество вариантов} = 3 \times 2^6 \] \[ \text{Общее количество вариантов} = 3 \times 64 \] \[ \text{Общее количество вариантов} = 192 \]

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

Ответ:

192