2
1

Есть 100 городов, часть из них соединенных авиалиниями. Доказать, что среди них есть 2 города, для которых существует не менее 50 городов, каждый из которых либо соединен с данными 2-мя городами, либо не соединен ни с одним.

задан 4 Мар 2:46

10|600 символов нужно символов осталось
2

пусть у нас есть граф на $%n =2m$% вершинах, ребра которого покрашены в 2 цвета. Будем называть уголок монохромным , если оба его ребра одного цвета. Пусть к какой либо вершине примыкают $%k $% ребер 1-го цвета и $%n-1-k $% ребер 2-го цвета. Тогда всего к этой вершине примыкают не менее $%A $% монохромных уголков: $$C_k^2+C_{n-1-k}^2 \ge C_m^2+C_{m-1}^2=A$$ Всего монохромных уголков не менее $%nA $%. Поэтому будет ребро на котором будут базироваться не менее: $$\dfrac {nA}{C_n^2}=\dfrac {2 (m-1)^2}{2m-1}$$ монохромных уголков.

ссылка

отвечен 4 Мар 17:46

1

@Sergic Primazon: наверное, такое рассуждение и имелось в виду, но оно даёт оценку 49, а не 50.

(4 Мар 19:29) falcao

@falcao тогда какое решение правильное?

(13 Май 7:53) Evgeny Kondr...

@Evgeny Kondr...: тут всего одно решение, и я думаю, что оно правильное в том смысле, что "выжимает" максимум возможного. Но в условии, судя по всему, что-то недоработано. Скажем, если городов всего два (случай m=1), то непонятно, какой город должен найтись.

(13 Май 9:32) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×447
×151

задан
4 Мар 2:46

показан
124 раза

обновлен
13 Май 9:32

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru