Решение задачи 402

Условие:

Есть проволока длиной 120 сантиметров. На какое наименьшее число частей нужно ее разрезать, чтобы из них можно было сложить каркас куба с ребром 10 сантиметров? (проволоку можно сгибать)

Решение:

Оценка:

Каркас куба можно представить, как граф на 8 вершинах. Степень каждой вершины равна 3. Допустим, мы уже как-то разрезали проволоку и можем сложить из частей каркас куба. Будем называть эти части путями. Каждое ребро графа может принадлежать только одному пути, поскольку иначе не хватило бы суммарной длины проволоки на весь оставшийся каркас. Что происходит, когда мы удаляем произвольный путь из графа? Либо степени двух вершин (начала и конца пути) уменьшаются на нечетное число (на 1, если во время прохождения пути мы больше не возвращаемся в эти вершины, и на 3, если мы проходим через вершины дважды) в случае, когда начало и конец -- это две разные вершины. Либо степень одной вершины (начала и конца) уменьшается на 2. Степень каждой промежуточной вершины (которая не является ни началом, ни концом) уменьшается на 2 в обоих случаях. Мы видим, что каждый путь изменяет четность степени не более двух вершин. Изначально 8 вершин нечётной степени. После удаления всех путей должно быть 8 вершин нулевой степени (необходимо изменить степень 8 вершин). Значит всего будет хотя бы 4 путя.

Пример:

Ответ: 4.