У Ивана было 4 сына, а дочерей не было. Его потомки тоже не имели дочерей, среди них у 15 было по 3 сына, у 16 — по 4 сына, а остальные вообще не имели детей. Сколько потомков…
У Ивана было 4 сына, а дочерей не было. Его потомки тоже не имели дочерей, среди них у 15 было по 3 сына, у 16 — по 4 сына, а остальные вообще не имели детей. Сколько потомков было у Ивана?
Решение по шагам
Моделируем ситуацию как дерево: корень — Иван. Любой человек, у которого были дети, считается внутренним узлом; остальные — листья. Вдобавок сказано, что у потомков не было дочерей, значит все дети — сыновья.
Во всём дереве есть:
- Иван имеет 4 сыновей → 4 ребра от корня.
- Среди потомков 31 узел имел детей: 15 узлов по 3 сына и 16 узлов по 4 сына.
- Остальные узлы не имели детей.
Всего ребёр (то есть общее число рождённых сыновей) равно сумме числа детей всех внутренних узлов: 4 (от Ивана) + 15·3 + 16·4 = 4 + 45 + 64 = 113.
В дереве для любого корня выполняется E = N − 1, где E — число ребер, N — число узлов (людей, включая Ивана). Тут E = 113, значит N = 114.
Потомков Ивана — это все узлы помимо самого Ивана: N − 1 = 114 − 1 = 113.
Ответ: у Ивана было 113 потомков.
