Пусть R(m, n) — наименьшее число людей в группе, которое гарантирует наличие m попарно знакомых или n попарно незнакомых. Эти числа определены при целых положительных m, n, при этом считаем R(m, 1) = R(1, n) = 1 (любой человек считается за одноэлементную группу попарно знакомых, а также попарно незнакомых). Докажите, что R(m, n) 6 R(m − 1, n) + R(m, n − 1).

задан 28 Дек '18 0:31

1

Это стандартный факт. Пусть имеется граф с N>=R(m-1,n)+R(m,n-1) вершинами. Его рёбра раскрашены в 2 цвета (красный, синий) по принципу знакомства или незнакомства. Из любой вершины исходит N-1 ребро. Если красных рёбер достаточно много, не меньше R(m-1,n), то рассматриваем их концы. В подграфе находим или красный граф на m-1 вершине, который вместе с начальной точкой даёт красный граф с m вершинами, либо находим синий n-граф. Аналогично, если есть >=R(m,n-1) синих рёбер. А если ни то, ни другое, то рёбер выходит не больше R(m-1,n)-1+R(m,n-1)-1=N-2 -- противоречие.

(28 Дек '18 0:55) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×1,291
×489
×156

задан
28 Дек '18 0:31

показан
98 раз

обновлен
28 Дек '18 0:55

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

по почте:

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

по RSS:

Ответы

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

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