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

Проект МЦНМО
при участии
школы 57
Задача 109782
Темы:    [ Деревья ]
[ Полуинварианты ]
[ Перестройки ]
[ Неравенство Коши ]
[ Алгебраические неравенства (прочее) ]
Сложность: 5-
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Дано дерево с n вершинами,  n ≥ 2.  В его вершинах расставлены числа x1, x2, xn, а на каждом ребре записано произведение чисел, стоящих в концах этого ребра. Обозначим через S сумму чисел на всех рёбрах. Докажите, что  


Решение 1

  Рассмотрим ребро l, соединяющее вершины с числами xi и xj. Обозначим через ki(l) число вершин, из которых нельзя пройти в вершину xi при удалении ребра l.
  Ясно, что   1 ≤ ki(l), kj(l) ≤ n – 1,  ki(l) + kj(l) = n.  Кроме того, для каждого i сумма     равна  n – 1  (сумма берётся по всем рёбрам l, выходящим из xi), так как из вершины xi можно пройти по рёбрам дерева в каждую из оставшихся  n – 1  вершин единственным несамопересекающимся путем.
  Согласно неравенству Коши для данного ребра l получим  
  Последнее неравенство верно, так как  ki(l)kj(l) = ¼ ((ki(l) + kj(l))² – (ki(l) – kj(l))² ≥ ¼ (n² – ((n – 1) – 1)²) = n – 1.
  Сложив неравенства (*) по всем рёбрам, получим требуемое неравенство.


Решение 2

  Будем проводить операции, не изменяющие чисел в вершинах и не уменьшающие сумму S чисел на рёбрах. Достаточно доказать неравенство по окончании этих операций.
  Вначале заменим числа в вершинах на их модули, то есть далее считаем, что x1, x2, ..., xn ≥ 0.
  Выберем наибольшее из чисел xi, пусть это число x1. Если нашлась вершина с числом xi,  i ≠ 1,  из которой выходит ровно одно ребро l, ведущее в вершину xj,  j ≠ 1,  то произведём перестройку: удалим ребро l и соединим ребром вершины с числами xi и x1. Полученный граф остаётся деревом, так как количество рёбер не изменилось и по-прежнему из каждой вершины можно пройти по рёбрам в любую другую. После перестройки сумма S изменяется на  xix1xixj ≥ 0.  Производим перестройки, пока это возможно. Поскольку при каждой перестройке число рёбер, выходящих из вершины с числом x1, увеличивается, через конечное число шагов мы придём к ситуации, когда невозможно сделать перестройку. Это означает, что вершина с числом x1 соединена ребром с каждой из оставшихся  n – 1  вершин.
  Таким образом, для конечной ситуации   S = x1x2 + x1x3 + ... + x1xn.  При этом неравенство верно, поскольку

     

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2003
Этап
Вариант 5
Класс
Класс 10
задача
Номер 03.5.10.3

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

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