|
|
 |
Условие
В основании призмы лежит n-угольник. Требуется раскрасить все 2n её вершин тремя красками так, чтобы каждая вершина была связана рёбрами с вершинами всех трёх цветов.
а) Докажите, что если n делится на 3, то такая раскраска возможна.
б) Докажите, что если если такая раскраска возможна, то n делится на 3.
Решение
а) Раскрасим вершины одного основания в таком порядке: красная, синяя, зелёная; красная, синяя, зелёная и т. д. Соответствующие вершины второго основания раскрасим в те же цвета.
б) Пусть есть r рёбер, у которых один конец синий, другой – красный. Из каждой красной вершины выходит ровно одно такое ребро, поэтому красных вершин ровно r. Точно так же синих – ровно r, то есть синих и красных вершин поровну. Аналогично количество красных вершин равно количеству зелёных, то есть трети количества вершин призмы (а их 2n). Поэтому 2n (а значит, и n) делится на 3.
Замечания
1. Баллы: 2 + 3.
2. Ср. с задачей 98265.
