Наименьшее из таких N называется числом Рамсея и обозначается R(n, k). Несложно доказать, что R(n,k) <= R(n-1,k) + R(n,k-1). В самом деле, обозначив R(n-1,k)=A, R(n,k-1) = B, рассмотрим произвольные A+B человек. Покажем, что среди них найдется либо n попарно знакомых, либо k попарно незнакомых. Выберем любого, скажем Васю. Вася или знаком хотя бы с A людьми, или незнаком хотя бы с B (потому что без него людей ровно A+B-1). В первом случае по определению числа A=R(n-1, k) среди его знакомых найдется либо n-1 попарно знакомых (добавив к ним знакомого с ними Васю, получим n попарно знакомых), либо k попарно незнакомых и сразу имеем то, что надо. Второй случай аналогичен.

Отсюда последовательно получаем неравенства R(2, n) <=n, R(3, n) <= n(n+1)/2 и т.д. При k=n получим оценку: R(n, n) < 4n, т.е. из любых 4n человек можно выбрать n попарно знакомых или попарно незнакомых. Насколько точна эта оценка? Наилучшую нижнюю оценку получил Эрдёш: из 2n/2 людей, n попарно знакомых или попарно незнакомых найдутся не всегда.

Доказательство удивительно просто: проверяем, что годится случайная компания! Пусть n – четно и выберем N=2n/2 людей. Каждых двух знакомим, если подброшенная для них монетка упадет орлом. Вероятность того, что данные n людей попарно знакомы (и попарно незнакомы), равна (1/2)n(n-1)/2. Складывая по всем наборам из n людей, получим число, меньшее 1 (вычисления опустим), и с положительной вероятностью наша компания не содержит ни n попарно знакомых, ни n попарно незнакомых людей.

 

Новости

20.05.2025 20 мая прошел 2 тур семейной математической онлайн-олимпиады 2025 года

Изображение для новости

Участниками тура стали 18 семейных команд из  Гаврилов-Ямского,  Тутаевского и Ярославского районов Ярославской области, г.Рыбинска, г.Ярославля, города Глазов (Удмуртская Республика),  г.Губахи (Пермский край),  г.Костромы.
Рейтинг участников опубликован на странице Итоги 2 тура.

 

17.05.2025 17 мая состоялся 1 тур семейной математической онлайн-олимпиады 2025 года

Изображение для новости

Участниками тура стали 42 семейные команды из Брейтовского, Гаврилов-Ямского, Некрасовского и Тутаевского районов Ярославской области. г.Рыбинска, г.Ярославля, села  Таволожка (Саратовская область),  г.Губахи (Пермский край), г.Долгопрудного (Московская область), г.Костромы, поселка Сетово (Тюменская область). Рейтинг участников опубликован на странице Итоги 1 тура.