У Ивана было 4 сына, а дочерей не было. Его потомки тоже не имели дочерей, среди них у 15 было по 3 сына, у 16 — по 4 сына, а остальные вообще не имели детей. Сколько потомков было у Ивана?

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