Олимпиадная задача: раскраска концов спичек — теория графов, 7-10 класс
Задача
На столе лежат несколько тонких спичек одинаковой длины. Всегда ли можно раскрасить их концы а) в 2, б) в 3 цвета так, чтобы два конца каждой спички были разных цветов, а каждые два касающихся конца (разных спичек) – одного и того же цвета?
Решение
а) Достаточно взять три спички и сложить из них правильный треугольник. Предположим, что нам удастся раскрасить его вершины в два цвета. Какие-то две вершины окажутся одного цвета, а значит, у спички, которая соединяет эти вершины, оба конца будут одного цвета. Противоречие. б) Сложим из 11 спичек конструкцию, изображённую на рисунке. Если бы удалось раскрасить семь вершин этой фигуры в три цвета, то какие-то три вершины оказались бы одного цвета. Несложно проверить, что и в этом случае найдётся спичка, оба конца которой имеют один и тот же цвет.
Ответ
а-б) Не всегда.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь