Случай с двумя вершинами очевиден. Далее рассматриваем случаи с большим числом вершин.
Пойдем от противного: пусть не так, и все висячие вершины покрашены в синий цвет.
Подвесим дерево за какую-нибудь красную вершину (такая обязательно существует, т.к. красных вершин не меньше, чем синих).
Получим, что цвет всех вершин уровня 0 красный. Но тогда, в силу того, что смежные вершины имеют разные цвета, цвет уровня 1 синий. Аналогично, цвет уровня 2 красный и т.д.
То есть цвета вершин на каждом из уровней одинаковы, и при этом на четных уровнях цвет вершин красный, а на нечетных - синий.
Степень красной вершины уровня 0 не может быть равна единице, т.к. все висячие вершины по предположению синие. Значит, ее степень не меньше двух, откуда число вершин уровня 1 не меньше двух - т.е. больше числа вершин уровня 0.
Рассмотрим пару из красного уровня 2k и синего уровня 2k+1, k∈N. Рассмотрим вершину красного уровня. Ее степень не меньше единицы (благодаря родительской вершине уровня 2k-1). Но при этом, т.к. все висячие вершины по предположению синие, ее степень должна быть не меньше двух - т.е. из нее выходит не менее одной дочерней синей вершины. Повторяя эти рассуждения для каждой из вершин уровня 2k, получим, что число вершин синего уровня не меньше числа вершин красного уровня.
Повторяя эти рассуждения для оставшихся уровней и учитывая, что число вершин уровня 1 больше числа вершин уровня 0, получим, что число синих вершин больше числа красных вершин - противоречие.
Значит, предположение неверно, и хотя бы одна из висячих вершин покрашена в красный цвет.
Ч.т.д.
Третье число равно 156.
Объяснение:
Найти третье число из записанных Артуром трех чисел, состоящих их цифр 1, 3, 5, 6, 8, 9.
Известно, что:
записаны три числа из цифр 1, 3, 5, 6, 8, 9; каждая цифра используется только один раз;второе число в 2 раза больше первой;третье число в 2 раза больше второго.Определить третье число.
1) Из условия "Второе число в два раза больше первого, третье число в два раза больше второго" следует:
второе и третье числа - это четные числа, так как они получаются умножением предыдущего числа на 2.
Значит, второе и третье числа оканчиваются на 6 или 8.
Тогда третье число нечетное, так как четных цифры в списке только две.
2) Что нам дает условие "третье число в два раза больше второго"?
Если второе число оканчивается на цифру 6, то третье число должно оканчиваться на цифру 2:
6 · 2 = 12.
Но цифры 2 в списке нет.
Значит второе число оканчивается на цифру 8, а третье - на цифру 6.
3) Условие "Второе число в два раза больше первого".
Определим последнюю цифру первого числа.
При делении числа, оканчивающегося на 8, получается последняя цифра 4 или 9:
8 : 2 = 4; 18 : 2 = 9; 28 : 2 = 14 и т.д.
Цифры 4 в списке нет. Первое число оканчивается на 9.
4) Подведем промежуточный итог.
Имеем три числа: ...9, ...8, ...6.
И остались четыре цифры.
Следовательно, первое и второе числа двузначные, а третье, как самое большое, - трехзначное.
5) Чтобы получить из двузначного числа трехзначное, число десятков в двузначном числе должно быть больше или равно 5.
У нас таких цифры две: 5 и 7.
Допустим, второе число 58 (число десятков в нем 5).
Тогда третье число равно 58 · 2 = 116.
Но цифра 1 не может использоваться дважды!
Тогда второе число имеет 7 десятков и оно равно 78.
6) Найдем оставшиеся два числа.
78 · 2 = 156.
78 : 2 = 39.
Итак, числа, записанные Артуром:
39, 78, 156.
Все цифры использованы по одному разу, выполняется соотношение "Второе число в два раза больше первого, третье число в два раза больше второго".
В ответ запишем третье число: 156.
