|
||||||||||||||||||
|
Содержание156Kонкурсная задача ММ156 (ТГ-3) (5 баллов) На занятии по дискретной математике на доске был изображен некоторый граф. Вася Пупкин записал в тетрадку количество вершин и ребер каждой связной компоненты графа, а также степени вершин самой большой (по количеству вершин) компоненты. Но само изображение графа он срисовать забыл. Кроме того, он забыл, за какую именно из вышеперечисленных характеристик отвечает каждое из записанных чисел. Сможет ли Вася решить домашнее задание «Найти диаметры каждой связной компоненты», если у него в тетрадке записаны числа: 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 6, 9? Решение Приведу решение Евгения Гужавина: Из анализа чисел последовательности видно, что:
1. В самой большой компоненте связности (КС) чётное число вершин, т.к. количество чисел в последовательности чётно.
Теперь известно, что граф имеет три КС и в большей из них шесть вершин и девять рёбер. Для того, чтобы найти пары чисел (количество вершин, количество рёбер) оставшихся КС, используем тот факт, что количество рёбер графа равно полусумме степеней вершин. В нашем случае сумма оставшихся десяти чисел последовательности равна 31, значит нужно проверить все группы по четыре числа, дающие в сумме 13:
В итоге имеем два варианта разделения чисел заданной последовательности: {(3,2),(4,4),(6,9),(1,2,3,3,4,5)} и {(3,3),(4,3),(6,9),(1,2,2,4,4,5)}. Обсуждение Легко убедиться, кто трехвершинная и шестивершинная компоненты определены условиями задачи однозначно, а для четырехвершинной существуют два варианта. Некоторые участники остановились на этом моменте, другие ограничились констатацией факта, что диаметр каждой компоненты определен однозначно. В связи с этим я испытывал затруднения, оценивая решение, в котором утверждалось, что существует более одного графа, со степенями вершин 1, 2, 3, 3, 4, 5. С одной стороны, это не так, а с другой - никак не влияет на ответ. Я думаю наиболее проницательные читатели догадаются, стал ли снижать оценку за этот промах. Удовлетворю любопытство одного из участников Марафона: расскажу, как я сочинял задачу ММ156. Каюсь, я делал это совершенно неправильно. Мне просто было интересно, что получится при таком подходе. Сначала я сочинил текст условия. Но без вопроса, что надо найти. А затем написал «от фонаря», не имея в виду ни одного конкретного графа, 12 чисел (даже то, что их именно 12 выяснилось позже, когда я их пересчитал). Затем провел анализ, наподобие тех, что проводили участники, решившие задачу. Я полагал, что для получения содержательной задачи придется сделать несколько попыток. Однако первый же набор чисел привел к ситуации, когда граф определен неоднозначно, но количество компонент и их диаметры можно восстановить. Награды За правильное решение задачи ММ155 Виктор Филимоненков, Олег Полубасов, Сергей Половинкин, Алексей Волошин, Евгений Машеров, Евгений Гужавин, Дмитрий Пашуткин, Николай Дерюгин и Анатолий Казмерчук получают по 5 призовых баллов. Эстетическая оценка - 4.7 балла Разбор задачи ММ156 подготовил Владимир Лецко
|
|||||||||||||||||
|
||||||||||||||||||
|