|
||||||||||||||||||
|
Содержание№116Задача ММ116 навеяна обсуждением одной из последовательностей в OEIS. Конкурсная задача ММ116 (10 баллов)
Сколько существует связных графов, таких что произведение степеней вершин равно:
а) сумме степеней вершин; Решение а) Приведу решение Юрия Вольвовского (впрочем, решения некоторых других участников, по сути идентичны).
Сначала докажем, что связный граф, у которого произведение степеней вершин не
больше их суммы, является деревом. Ответ к пункту а): 3 графа. б) Докажем, что множество требуемых графов бесконечно. Для этого укажем алгоритм построения бесконечной серии подходящих графов. Легко убедиться, что дерево, у которого 7 из 10 вершин являются висячими, а три остальных имеют степени 3, 4, 4, удовлетворяет всем условиям пункта б). Это дерево (на самом деле таких деревьев 3, но для нас это не важно) будет открывать нашу серию. Положим x0=4, y0 = 4, xk = yk-1, yk = 3yk-1-xk-1-1. Легко убедиться (по индукции), что дерево, у которого три вершины, не являющиеся висячими, имеют степени 3, xk, yk при любом натуральном будет удовлетворять условиям пункта б). Ответ к пункту б): бесконечно много графов. Обсуждение С первом пунктом участники в целом справились успешнее, чем со вторым. Основным недоостатком здесь была потеря одновершинного дерева. Учитывая вырожденность этого случая (его и деревом-то называть странно:)), я не снижал оценок за этот момент. Очевидно, что построенная нами бесконечная серия графов, не исчерпывает всех графов, удовлетворяющих условиям пункта б). Каждое дерево с тремя узловыми вершинами, удовлетворяющее условиям пункта б) порождает серию, аналогичную описанной. Например, стартуя с дерева со степенями узловых вершин 4, 4, 12 положим x0=4, y0 = 12, xk = yk-1, yk = 4yk-1-xk-1-1. Деревья со степенями узловых вершин (4, xk, yk) будут обладать требуемыми свойствами. В отличие от пункта a), графы из пункта б) не обязаны быть деревьями. Очевидным примером служит четырехзвенный цикл. Юрий Вольвовский указал красивый способ получать новые подходящие графы из любого графа, удовлетворяющего условию пункта б), а не только из деревьев с тремя узловыми вершинами. На любом ребре такого графа возьмем новую вершину (выражаясь аккуратнее, заменим ребро конструкцией ребро-вершина-ребро) и подвесим к ней еще x-4 вершины, где x - произведение степеней вершин исходного графа. Тривиально проверяется, что полученный граф будет подходящим. Награды
За решение задачи ММ116 участникам начислены следующие призовые баллы: Эстетическая оценка задачи - 4.8 балла
|
|||||||||||||||||
|
||||||||||||||||||
|