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

Условие:

У куба отмечены вершины и центры граней, а также проведены диагонали всех граней. Можно ли по отрезкам этих диагоналей обойти все отмеченные точки, побывав в каждой из них ровно по одному разу?

Решение:

Покрасим все вершины куба в красный цвет, а центры граней в синий:

Видно, что при такой раскраске любое ребро (половины фиолетовой диагонали) соединяет вершины разного цвета. Поэтому вершины такого графа можно разделить на две группы - красные и синие:

Причем любое ребро соединяет только красную и синюю вершину (ребер, соединяющих одноцветные вершины нет). Такой граф называется двудольным.

Предположим, что существует обход всех вершин без повторения. Пусть он начинается в красной вершине (по сказанному далее будет понятно, что это не принципиально). После каждого шага цвет вершины меняется. Значит рано или поздно мы попадем в последнюю синюю вершину, в которой мы еще не побывали к этому моменту. После нее мы перейдем в какую-то красную вершину.

Поскольку красных вершин на две больше, чем синих, то в этот момент будет еще одна красная вершина (в зеленом кружочке), в которой мы еще не были. Поскольку граф двудольный, то на следующем ходу мы обязаны перейти в синюю вершину, но во всех синих вершинах мы уже бывали ранее. Противоречие. Значит такого обхода вершин не существует.

Ответ: нет.