ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 30812
Темы:    [ Деревья ]
[ Четность и нечетность ]
[ Доказательство от противного ]
Сложность: 4-
Классы: 8
В корзину
Прислать комментарий

Условие

Расстоянием между двумя произвольными вершинами дерева будем называть длину простого пути, соединяющего их. Удалённостью вершины дерева назовём сумму расстояний от неё до всех остальных вершин. Докажите, что в дереве, у которого есть две вершины с удалённостями, отличающимися на 1, нечётное число вершин.


Решение

Соединим эти две вершины A и B путем. Пусть a – его длина. Расстояние от любой вершины до A и B отличаются на величину, имеющую ту же чётность, что и a. Поэтому если число вершин чётно, то (независимо от чётности a) удаленности A и B отличаются на чётное число, что противоречит условию.

Источники и прецеденты использования

книга
Автор Генкин С.А., Итенберг И.В., Фомин Д.В.
Год издания 1994
Название Ленинградские математические кружки
Издательство Киров: "АСА"
Издание 1
глава
Номер 13
Название Графы-2
Тема Теория графов
задача
Номер 034

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .