На рисунке показан абажур, изготовленный из стальной проволоки. Какое наименьшее количество кусков проволоки нужно, чтобы изготовить абажур, показанный на рисунке?
Источник: fioco.ru
Cпособ 1
Решение:
Абажур состоит из трёх окружностей (верхней и двух нижних) и четырёх боковых Г-образных кусков. Однако можно минимизировать количество частей.
Если верхняя окружность плавно переходит в один из боковых элементов, затем в нижнюю большую окружность, а затем через точку касания с другим боковым элементом переходит в нижнюю прямую линию, замыкая малую нижнюю окружность, то это составит один длинный кусок.
Оставшиеся три боковых Г-образных куска завершают конструкцию. Таким образом, минимально возможно использовать 4 куска проволоки.
Ответ: 4.
Cпособ 2
Решение:
Абажур можно рассмотреть как граф с 12 вершинами. В 8 из них сходятся по 3 ребра – это вершины нечетной степени, а в 4 вершинах сходятся по 4 ребра – это вершины четной степени.
Из теоремы следует, что если в графе существует путь, проходящий через все ребра ровно один раз, то в нем не больше двух вершин нечетной степени.
В нашем случае вершин нечетной степени 8, что больше двух. Значит, граф нельзя обойти одним куском проволоки, а потребуется не менее 8÷2 = 4 кусков.
Пример разбиения на четыре куска проволоки приведен в решении первым способом.
Ответ: 4.