Дано: бинарное дерево с n > 3 вершинами.
Найти: показать, что количество цепей максимальной длины в этом дереве чётно.
Решение:
1. Пусть h - высота дерева. Максимальная длина цепи (путь) в бинарном дереве равна h.
2. В бинарном дереве существует 2 вида цепей: цепи, которые начинаются с листа и заканчиваются в листе.
3. Количество цепей максимальной длины h можно представить через количество листовых вершин на уровне h. Каждая вершина на уровне h-1 может давать 2 цепи, т.е. количество цепей максимальной длины будет зависеть от количества вершин на уровне h-1.
4. Если высота дерева h > 1, то на уровне h-1 может быть от 1 до 2^(h-1) вершин. Если у нас 2k вершин, то количество цепей будет 2k, что чётно.
5. Если h = 2, в дереве есть 3 вершины. Мы имеем 2 листа и 1 внутреннюю вершину, что даёт 1 цепь. Если h > 2, цепей станет больше и будет парное количество.
Ответ: количество цепей максимальной длины в бинарном дереве с n > 3 вершин чётно.