Решение задачи 303
Петров СергейУсловие:
У куба отмечены вершины и центры граней, а также проведены диагонали всех граней. Можно ли по отрезкам этих диагоналей обойти все отмеченные точки, побывав в каждой из них ровно по одному разу?
Решение:
Покрасим все вершины куба в красный цвет, а центры граней в синий:
![](/file/984fdd3eac651b760732e.png)
Видно, что при такой раскраске любое ребро (половины фиолетовой диагонали) соединяет вершины разного цвета. Поэтому вершины такого графа можно разделить на две группы - красные и синие:
![](/file/0e1c4cedb3c9bf6b8041a.png)
Причем любое ребро соединяет только красную и синюю вершину (ребер, соединяющих одноцветные вершины нет). Такой граф называется двудольным.
Предположим, что существует обход всех вершин без повторения. Пусть он начинается в красной вершине (по сказанному далее будет понятно, что это не принципиально). После каждого шага цвет вершины меняется. Значит рано или поздно мы попадем в последнюю синюю вершину, в которой мы еще не побывали к этому моменту. После нее мы перейдем в какую-то красную вершину.
![](/file/29c62fc5cd101870b95fa.png)
Поскольку красных вершин на две больше, чем синих, то в этот момент будет еще одна красная вершина (в зеленом кружочке), в которой мы еще не были. Поскольку граф двудольный, то на следующем ходу мы обязаны перейти в синюю вершину, но во всех синих вершинах мы уже бывали ранее. Противоречие. Значит такого обхода вершин не существует.
Ответ: нет.