Вероятностный метод (усреднение)

Переведём задачу сразу на язык графов так, что человек — вершина, а рёбра(антирёбра) — знакомство(незнакомство). Заметим, что при задача очевидна, поэтому будем считать, что Рассмотри число которое меньше, чем Тогда всего графов на вершинах Идея доказательства следующая: если графов, содержащих клику, (аналогично для антиклик), то существует граф, в котором нет ни того, ни другого, а значит Всего графов на вершинах, содержащих клику на данных вершинах, Следовательно, всего графов размера содержащих клику:

Последнее выражение меньше, чем если Легко доказать (по индукции например), что при Поэтому можно взять так, как

А значит и что и требовалось.