27. Научная переписка

Шесть ученых А, B, С, D, Е и F переписывалисЬ друг с другом по двум научным темам. Каждый переписывался с каждым по одной тЕМе. Докажите, что найдутся трое ученых, переписывающихся между собой по одной и Той же Теме.

В самом деле, учеНЫй А перЕПисывается с 5 коллЕГами. По каким бы темам ОН с ними НИ вел переписку, найДутся трое учеНЫх (например, В, С, D), с которымИ Он ПерепИСывается по одНОй и той же тЕМе (например, по первой). Если хотя бы двое из этих трех ученых Переписываются по первой теме, то, присоедиНиВ к ним А, полУЧиМ Тройку переписывающихся по первой теме. Если же никто из троих не переписывается друг с другом по Первой Теме, то они пЕРеписываются по второй теме, и мы снова получилИ тройку учеНЫх, переписка которых Посвящена Одной и той же теме.

Если бы число ученых было меНЬше 6, то Утверждение Уже не было бы верным — можНО так оргаНИзовать Переписку, чтобы НИкакая тройка Не заНИмалась Одной И той же темой. НапрИМер, достаточно, чтобы из ученых A, B, С, D и Е по ПЕрвой теме вели переписку А с В и С, B с D, C C E, а Остальные пары интересовались второй темой.

Если изобразить ученых точками, а темы их перепИСки — цветами отрезков (оДин цвет для первой темы, а вторОй — для другой), то доказанное выше утверждение можно сформулировать следующим образом.

Если 6 точек соединены попарно отрезками, окрашенными в два различных цвета, то найдутся 3 точки, являющиеся вершинами одноцветного треугольника.

Мы могли бы окрашивать отрезки не в 2, а, скажем, в 3 различных цвета. В этоМ случае пришлось бы взять большЕ точек — не 6, а 17. Например, Если 17 ученых переписываются друг с друГОм по трем различным научным темам, причем каждая пара ученых ведет переписку лишь по одной теме, то всегда найдутся трое ученых, переписывАющихся по одной и той же теме.

В самом деле, каждый учеНЫй ведет переписку с 16 другими. Поэтому для ученого А найдутся еще 6 человек, с которыми он переписывается на одну и ту же тему. Если хотя бы одна пара из этих 6 переписывается друг с другом на ту же тему, то искомая тройка ученых найдеНА. Если же Они переписываются друг с другом лишь по двум оставшимся темам, то, по ДОказанному выше, среди них НАйдутся трое, переписка которых посвящена одной теме.

Читатель легко найдет теперь ДлЯ любого числа тем такое количество ученых, что при любом распределении тем между ними можно выбрать тройку, переписывающуюся по одному и тому же вопросу. Но это утверждение моЖНо обобщить еще дальше, разыскивая не тройки, а, скажем, четверки ученых. В этом случае при переписке по двум темам достаточно взять 18 учеНЫх, чтобы из них можно было выделить четверку ученых с общей тематикой переписки. А 17 ученых уже недостаточно: возьмем 17 учеНЫх, занумеруем их числами от 1 до 17 и отдадим первую тему парам ученых (I, J), для которых равно одНОму из чисел 1, 2, 4, 8, 9, 13, 15, 17, а вторую тему — остальным парам ученых. Сделайте рисунок и убедитесь, что ни одна четверка ученых не ведет переписку по общей теме.

Но путь обобщений еще не закончен. Ведь можно придать темам различный вес и искать, например, для первой темы четверки ученых, а для второй — тройки ученых. Тогда необходимое число окажется больше 6, но меНЬше 18 — оно равно 9. Кроме того, ученых можно разбивать не на пары, а на коллективы из большего числа участников и закреплять тему за каждым таким коллективом.

Тогда данная пара уЧЕных может, например, обсуЖДать первую тему в одном коллективе, а вторую — в другом.

АНГлийский матЕМатик Рамсей доказал общую Теорему. Она утверждает, что Если ЗАданы число тем т и число участников в каждом Коллективе R и если теме с номером K Сопоставлено число , , то при достАТочно большом числе частникоВ и любом распределении тем между коллективами можно найти тему C номЕРОм K и ученых, любые r из которых ЗАняты Этой Темой.

< Предыдущая		Следующая >