Вот мы решили провести еще один интересный эксперимент. Опять набрали шесть случайных людей на Физтехе. Сейчас мы узнаем, кто из них с кем знаком, а кто не знаком. Начнем. Как тебя зовут? -Антон. -Антон, так. Сейчас мы изобразим это в виде некоторой схемки. -Софья. -Софья. -Иван. -Иван. Видите, я выстраиваю в вершинах шестиугольника. -Андрей. -Андрей. -Динар. -Динар. -Андрей. -Андрей Шарапов. Значит, мы можем различить двух Андреев, будет Андрей Ш. и просто Андрей. Теперь мы будем узнавать, кто с кем знаком. Начнем с Антона. Назови, пожалуйста, с кем ты знаком из присутствующих людей. -С Иваном и Андреем. -Прекрасно. Андреем просто? Это мы изобразим вот такими вот стрелочками, соединяющими точки, обозначающие людей. Так, Софья из оставшихся четырех ребят с кем знакома? -Ни с кем. -Ни с кем. Значит, отсюда ни одна стрелочка не выходит. -Иван? -С Андреем. Из оставшихся — с Андреем, но который Андрей просто, без Ш.? -Просто. -Так, дальше Андрей. -С кем из Динара и Андрея Ш. знаком? -Ни с кем. Ни с кем. -Динар, знаком ли ты с Андреем Ш.? -Нет. Не знаком. Итак, значит, фокус в данном случае состоит в том, — и нам опять очень сильно повезло, что у нас есть как три попарно знакомых друг с другом (Антон, Иван и Андрей), так три незнакомых попарно друг с другом (Софья, Андрей Ш. и Динар). И это, конечно, великое чудо, но что можно утверждать в любом случае, это что, либо такую тройку я найду, либо вот такую. Но утверждать, что всегда найду обе, конечно, нельзя. Итак, сейчас я строго докажу следующий факт: что если мы возьмем совершенно произвольных шестерых людей, то среди них всегда найдутся либо три попарно знакомых, либо три попарно незнакомых. [ШУМ] Для доказательства я повторю эту конструкцию, только теперь у меня уже совершенно произвольные какие-то ребра существуют здесь, а каких-то ребер нет. Я не знаю — вот это вот условное, вот то, что нарисовал здесь, это условно, — поэтому на самом деле здесь-то я вот могу уже указать трех, но нужно объяснить, как я буду действовать в любом случае. я возьму наугад какого-нибудь одного из наших шестерых людей, возьму наугад, и посмотрю, со сколькими из остальных пятерых этот человек знаком. либо у него есть три знакомых или более, либо, наоборот, есть три незнакомых и более, то есть вот этих стрелок, которые выходят из него, может быть до пяти, их может быть от 0 до 5. Так вот, я разобью на два класса все случаи возможные. В первом случае это, значит, стрелок выходит 0, 1 или 2, а во втором случае — 3, 4 или 5. Давайте разберем их по очереди. В первом случае, когда не более двух знакомых у этого человека, я рассмотрю трех его не знакомых, трех не знакомых с ним. И теперь верно одно из двух: либо между ними есть хотя бы одна пара, которые друг с другом тоже не знакомы, либо они все трое знакомы друг другу. Если они все трое знакомы друг другу, то вот, пожалуйста, вот три попарно знакомых и всё. А если есть хотя бы два между ними незнакомых, то тройку попарно незнакомых я построю, привлекая вот этого первого человека. Он не знаком ни с этим, ни с этим, а эти двое не знакомы друг с другом, вот вам три. если бы эти трое были знакомы все попарно друг с другом, то этой тройки я бы не нашел, но зато я нашел бы такую тройку. Совершенно аналогично я рассматриваю случай вот этот. То есть если из вот этой точки ведет три или более стрелок, то я могу найти трех из оставшихся пятерых, которые знакомы вот с этим. либо хотя бы какие-то двое из них между собой знакомы — и тогда вот вам, пожалуйста, трое знакомых попарных, этот исходный и эти двое, — либо ни один из них не знаком с остальными двумя, и тогда вот, пожалуйста, вам тройка попарно незнакомых. Итого, все случаи разобраны, и во всех случаях доказан этот результат. Теперь я хочу рассказать про обобщения этого результата — довольно любопытные, потому что они выводят на некоторую нерешенную проблему в математике. Вот это доказанное утверждение в математическом мире записывается вот так: R(3, 3) = 6. Что же это за мистика? А это вот что за мистика. Какое минимальное количество людей надо взять, чтобы среди них всегда нашлось либо три попарно знакомых, либо три попарно незнакомых. Предлагаю, между прочим, слушателям построить пример пяти людей, таким образом знакомых друг с другом, что нельзя найти ни трех попарно знакомых, ни трех попарно незнакомых. Это очень просто, поэтому я даже не буду подсказывать. Итого, минимальное количество людей, которых нужно взять, чтобы было точно можно выбрать либо трех попарно знакомых, либо трех попарно незнакомых — это шесть. Вот для шести людей мы это только что доказали. Возникает обобщающий вопрос — математики занимаются обобщениями. Математики любят какую-то постановку взять и обобщить. а сколько надо взять людей, чтобы, скажем, среди них всегда можно было выбрать либо пять попарно незнакомых, то есть такую компанию из людей, никто друг друга не знает, либо семь попарно знакомых. И здесь можно поставить вообще любые числа. Оказывается, что, кроме очень простого случая, когда начинается с двойки, скажем 2, а дальше — 9, 10, что угодно, вот это будет просто, а уже начиная с трех, это не очень просто, а скажем, R(6, 6) просто неизвестно человечеству, и все последующие тоже. Неизвестно. Чему равно? То есть у нас есть совершенно открытая проблема: сколько надо набрать людей, чтобы гарантированно среди них можно было выбрать либо шесть попарно знакомых, либо шесть попарно незнакомых. Открытая математическая проблема, хотя вроде бы она формулируется абсолютно тривиальным образом и понятна на уровне постановки, понятна всем людям, так сказать, на Земле. Но в дискретной математике таких проблем очень много, мы познакомимся в будущем с еще одной такой проблемой.
