Здравствуйте, Лека!
> Кстати, а доказательство где?
Вот оно.
Набор точек, называемых вершинами, некоторые из которых соединены между
собой линиями, называемых ребрами, называется графом. (извините за
тавтологию). Изобразим описанные в задаче условия в виде графа. Условимся
обозначать людей точками (вершины) и соединять эти точки линиями (ребра),
если люди знакомы; не соединять, если люди не знакомы. Нам нужно доказать,
что в графе есть вершина из которой выходит не менее 11 ребер. Предположим
противное: пусть из всех вершин выходит не более чем 10 ребер. Посмотрим, из
скольки вершин может выходить 0 ребер? Не более, чем из одной (иначе
найдутся люди, имеющие одинаковое число знакомых и не знакомые между собой).
Далее, из скольки вершин может выходить 1 ребро? Не более, чем из двух.
Аналогично, 2 ребра могут выходить не более, чем из 3 вершин и так далее, 10
ребер могут выходить не более чем из 11 вершин. Получаем, что всего вершин
не более чем 1+2+3+...+11=66, а по условию задачи их 70. Получили
противоречие, значит наше предположение неверно и найдется вершина из
которой выходит не менее 11 ребер, что и требовалось доказать.
--
С уважением,
Алексей Устинов.
Номер выпуска : 26321
Возраст листа : 277 (дней)
Количество подписчиков : 138
Адрес в архиве : http://subscribe.ru/archive/rest.interesting.flame/msg/207486
Получить правила : mailto:rest.interesting.flame-rules@subscribe.ru
Формат "дайджест" : mailto:rest.interesting.flame-digest@subscribe.ru
Формат "каждое письмо" : mailto:rest.interesting.flame-normal@subscribe.ru
Формат "читать с веба" : mailto:rest.interesting.flame-webonly@subscribe.ru
-*Информационный канал Subscribe.Ru
Адрес подписки:
Написать в лист: mailto:rest.interesting.flame-list@subscribe.ru
Отписать: mailto:rest.interesting.flame--unsub@subscribe.ru
http://subscribe.ru/ http://subscribe.ru/feedback