Вершины дерева покрашены в красный и синий цвета так, что смежные вершины имеют разные цвета, и красных вершин не меньше, чем синих. Докажите, что хотя бы одна из висячих вершин покрашена в красный цвет. Требуется полное доказательство задачи. Решить до 3 февраля.
Ответы
Случай с двумя вершинами очевиден. Далее рассматриваем случаи с большим числом вершин.
Пойдем от противного: пусть не так, и все висячие вершины покрашены в синий цвет.
Подвесим дерево за какую-нибудь красную вершину (такая обязательно существует, т.к. красных вершин не меньше, чем синих).
Получим, что цвет всех вершин уровня 0 красный. Но тогда, в силу того, что смежные вершины имеют разные цвета, цвет уровня 1 синий. Аналогично, цвет уровня 2 красный и т.д.
То есть цвета вершин на каждом из уровней одинаковы, и при этом на четных уровнях цвет вершин красный, а на нечетных - синий.
Степень красной вершины уровня 0 не может быть равна единице, т.к. все висячие вершины по предположению синие. Значит, ее степень не меньше двух, откуда число вершин уровня 1 не меньше двух - т.е. больше числа вершин уровня 0.
Рассмотрим пару из красного уровня 2k и синего уровня 2k+1, k∈N. Рассмотрим вершину красного уровня. Ее степень не меньше единицы (благодаря родительской вершине уровня 2k-1). Но при этом, т.к. все висячие вершины по предположению синие, ее степень должна быть не меньше двух - т.е. из нее выходит не менее одной дочерней синей вершины. Повторяя эти рассуждения для каждой из вершин уровня 2k, получим, что число вершин синего уровня не меньше числа вершин красного уровня.
Повторяя эти рассуждения для оставшихся уровней и учитывая, что число вершин уровня 1 больше числа вершин уровня 0, получим, что число синих вершин больше числа красных вершин - противоречие.
Значит, предположение неверно, и хотя бы одна из висячих вершин покрашена в красный цвет.
Ч.т.д.