Наименьшее из таких 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 попарно незнакомых людей.

 

Новости

14.05.2023 Финал семейной математической олимпиады пройдет 23 мая в онлайн-режиме

Завершились отборочные туры семейной математической олимпиады "От А до Я". Участниками туров стали семейные  команды из Ярославской, Вологодской, Ивановской, Калининградской, Костромской, Липецкой, Московской, Самарской областей, Ставропольского и Пермского краев, г.Санкт-Петербурга и Республики Адыгея.

По техническим причинам финал семейной математической онлайн-олимпиады перенесен на  23  мая. Приглашенные к участию команды встретятся в режиме видеоконференцсвязи.

26.04.2023 В мае 2023 года состоится семейная математическая онлайн-олимпиада

Приглашаем семейные команды из Ярославской области и других регионов принять участие в  математической олимпиаде "От А до Я". Для участия  познакомьтесь с правилами, расписанием отборочных туров и  техническими особенностями участия в турах олимпиады, зарегистрируйте семейную команду, выберите удобное для своей команды время в расписании и попробуйте свои силы в командном решении нестандартных, занимательных и увлекательных задач. В составе команды должен быть обязательно хотя бы один школьник не младше 5 и не старше 8 класса!