Задача 32022

Темы:    [ Обход графов ] [ Обходы многогранников ] [ Степень вершины ] [ Четность и нечетность ]

Сложность: 3 Классы: 8,9,10

Условие

В одной из вершин  а) октаэдра;  б) куба сидит муха. Может ли она проползти по всем его рёбрам ровно по одному разу и возвратиться в исходную вершину?

Решение

а) Пусть, A, B, C, A₁, B₁, C₁ – вершины октаэдра, причём  (A, A₁),  (B, B₁)  и  (B, B₁) – пары противоположных вершин. Тогда любая пара вершин, кроме этих трёх, соединяется ребром. Путь мухи может быть следующим:  ABA₁C₁BCAC₁B₁CA₁B₁A  (см. рис.)

б) В каждой из восьми вершин куба сходится по три ребра. Это означает, что степень каждой вершины полученного графа нечётна, значит, путешествие совершить невозможно.

Ответ

а) Может;  б) не может.

Замечания

Источник решения: книга В.О. Бугаенко "Турниры им. Ломоносова. Конкурсы по математике". МЦНМО-ЧеРо. 1998.

Источники и прецеденты использования

олимпиада
Название	Турнир им.Ломоносова
год/номер
Номер	05
Дата	1982
задача
Номер	03