Скачать или смотреть Теория Рамсея

Докажите, что в любой компании из шести человек найдутся либо трое попарно знакомых, либо трое попарно незнакомых. (Считается, что если А знаком с Б, то Б знаком с А.) (Доказательство: Изобразим знакомства синими ребрами, а незнакомства — красными. Из каждой вершины исходит 5 ребер. По принципу Дирихле среди них найдутся 3 одноцветных. Рассмотрим образуемый ими вместе с инцидентными им вершинами подграф. Если провести в нем еще 1 ребро того же цвета, то все доказано. В противном случае это три вершины треугольника другого цвета.)

На доске отметили 17 точек и соединили каждые 2 из них цветным отрезком: белым, синим или красным. Докажите, что найдутся 3 точки в вершинах одноцветного треугольника. Подумайте, как можно обобщить эту задачу. (Доказательство: Из каждой вершины исходит 16 ребер. По принципу Дирихле среди них найдутся 6 одноцветных. Рассмотрим образуемый этими ребрами и инцидентными им вершинами подграф. Если провести в нем еще 1 ребро того же цвета, то все доказано. В противном случае имеем 6 вершин, на которых надо построить полный двуцветный граф, в каковом (см. предыдущую задачу) непременно найдется одноцветный треугольник. Обобщение: Для любого количества цветов n можно указать число вершин xn, которого будет достаточно, чтобы в построенном на них полном n-цветном графе нашелся одноцветный треугольник, причем x1 = 3; xn = n(xn – 1 – 1) + 2. Таким образом, эти значения образуют последовательность 3, 6, 17, 66, 327, 1958, 13701, 109602, ...)

ВК: https://vk.com/id2177613
Skype: Doka382
WhatsApp, Viber: +7-952-371-13-71
TikTok:   / dima_math  

Поддержать канал:

Сбербанк:
4817 7602 5094 7060

Альфа-Банк:
4584 4328 2354 8236

PayPal:
paypal.me/DmitriiMikhailov

Почта Банк:
2200 7702 5595 7682

Яндекс Деньги:
https://money.yandex.ru/to/4100110572...

ВТС:
1DimaeQ4DTk5mNLsShNqnCYpe2pDu1Gihf

DASH:
XdimonuW12MhgM6qq425WseraKbEwpQdf3

MONERO:
42iadV4NaTvWh9JuK4EVKdh1jPHExftG8dQh3jHnEnBjeAcD445xfJxDXSpTiA5LRWMAfXiQ17kaw7UxuerjXnQmQY9uy9e

DOGECOIN:
DDimonNctcjxGTTp78KUsf2ZrjbhN1mJw5