|
Пусть 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 
Orange |
Здравствуйте
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
28 Дек '18 0:31
показан
609 раз
обновлен
28 Дек '18 0:55
Связанные вопросы
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Это стандартный факт. Пусть имеется граф с 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 -- противоречие.