Разделы 
Дополнительно
Задача по математике - 3211
2019-05-27 
Можно ли ребра $n$ -угольной призмы раскрасить в 3 цвета так, чтобы на каждой грани были все 3 цвета и в каждой вершине сходились ребра разных цветов, если а) $n = 1995$; б) $n = 1996$.
Решение:
a) Покрасим ребра нижнего основания по кругу: 1-е в первый цвет, 2-е во второй, 3-е в третий, 4-е опять в первый и т. д. (1995 делится на 3, поэтому цепочка замкнется). Каждое ребро верхнего основания покрасим в цвет ребра нижнего основания, находящегося под ним. Каждое боковое ребро, выходящее из вершины, где сходятся два цвета, покрасим в недостающий цвет (рис.). Ясно, что на всех боковых гранях присутствуют все 3 цвета.
б) От противного, пусть призма покрашена требуемым образом; тогда в основании есть 3 ребра всех трех цветов, идущие подряд (иначе основание раскрашено с периодом 2 и не может быть покрашено в три цвета). Рассмотрим такую тройку и занумеруем цвета в ней по часовой стрелке. Несложно проверить, что раскраска этого участка однозначно определяет раскраску участка, находящегося над ним, соответствующих боковых ребер и следующих ребер основания (см. рис.). Мы видим, что следующее по часовой стрелке ребро основания имеет цвет 1.
Повторяя рассуждение, видим, что следующее ребро основания имеет цвет 2, и т. д. Таким образом, нижняя грань окажется покрашенной с периодом 3. Но 1996 не делится на 3 - противоречие.
Ответ: а) Можно; б) нельзя.
Можно ли ребра $n$ -угольной призмы раскрасить в 3 цвета так, чтобы на каждой грани были все 3 цвета и в каждой вершине сходились ребра разных цветов, если а) $n = 1995$; б) $n = 1996$.
Решение:
a) Покрасим ребра нижнего основания по кругу: 1-е в первый цвет, 2-е во второй, 3-е в третий, 4-е опять в первый и т. д. (1995 делится на 3, поэтому цепочка замкнется). Каждое ребро верхнего основания покрасим в цвет ребра нижнего основания, находящегося под ним. Каждое боковое ребро, выходящее из вершины, где сходятся два цвета, покрасим в недостающий цвет (рис.). Ясно, что на всех боковых гранях присутствуют все 3 цвета.
б) От противного, пусть призма покрашена требуемым образом; тогда в основании есть 3 ребра всех трех цветов, идущие подряд (иначе основание раскрашено с периодом 2 и не может быть покрашено в три цвета). Рассмотрим такую тройку и занумеруем цвета в ней по часовой стрелке. Несложно проверить, что раскраска этого участка однозначно определяет раскраску участка, находящегося над ним, соответствующих боковых ребер и следующих ребер основания (см. рис.). Мы видим, что следующее по часовой стрелке ребро основания имеет цвет 1.
Повторяя рассуждение, видим, что следующее ребро основания имеет цвет 2, и т. д. Таким образом, нижняя грань окажется покрашенной с периодом 3. Но 1996 не делится на 3 - противоречие.
Ответ: а) Можно; б) нельзя.
