На олимпиаду пришло 2018 участников, некоторые участники знакомы между собой. Будем говорить, что несколько попарно знакомых участников образуют «кружок», если любой другой участник олимпиады не знаком с кем-то из них. Докажите, что можно рассадить всех участников олимпиады по 90 аудиториям так, что ни в какой аудитории не сидят все представители какого-либо «кружка».
Докажем индукцией по k более общее утверждение: 2k аудиторий хватит для того, чтобы рассадить 
участников. Тогда для получения утверждения задачи достаточно будет подставить 
поскольку 
База 
Поскольку 
мы можем посадить каждого участника в отдельную аудиторию.
Пусть утверждение доказано, когда количество участников не больше 
Докажем утверждение, когда количество участников не больше 
Рассмотрим участника v с наибольшим числом d знакомых. Если 
то посадим v в одну аудиторию, всех его знакомых во вторую, а оставшихся
по предположению индукции мы можем рассадить в 
аудиторий так, что в этих аудиториях не будет «кружков». В первой аудитории только один человек, поэтому «кружков» там быть не может, во второй аудитории нет «кружков», так как там нет v, но он знаком со всеми из этой аудитории.
Если же 
то заметим, что нам заведомо хватит 
аудиторий. Выделим 
аудиторий и будем рассаживать участников по очереди так, чтобы никакие два знакомых не сидели в одной аудитории, тогда в одной аудитории не будут образовываться «кружки» (люди, сидящие в одной аудитории, не знакомы друг с другом). У каждого участника не больше чем d знакомых, так как аудиторий 
то всегда есть аудитория, где нет его друзей, куда мы его и посадим.
Комментарий.
В задаче речь идет о так называемом кликовом хроматическом числе графа. Если обычное хроматическое число - это минимальное число цветов, в которые можно так покрасить все вершины, чтобы концы любого ребра имели разные цвета, то кликовое хроматическое число — это тоже минимальное число цветов для покраски вершин, только теперь требуется, чтобы все полные подграфы (клики), которые максимальны по включению (то есть не содержатся внутри еще больших полных подграфов) были неодноцветными (имели хотя бы две вершины разного цвета). Естественно, исключаются изолированные вершины, то есть вершины, которые ни с кем не соединены ребрами. Ясно, что если в графе нет треугольников (клик, имеющих три и более вершин), то в нем все максимальные по включению клики, не являющиеся изолированными вершинами, суть его ребра, а значит, для такого графа кликовое хроматическое число совпадает с обычным. Любопытно то, что если обычное хроматическое число подграфа всегда меньше хроматического числа графа, то с кликовым хроматическим числом все, конечно, не так, ведь у полного графа оно равно двум, а, например, у нечетного простого цикла оно равно трем.
Задача отыскания точных оценок кликового хроматического числа как в общем случае, так и для многих важных классов графов весьма далека от своего решения. В нашем случае речь шла как раз о произвольном графе: фактически в задаче требовалось доказать, что кликовое хроматическое число произвольного графа на n вершинах не превосходит 
Сейчас наилучшая известная верхняя оценка 
и это лишь в константу раз лучше, чем требует наша задача. Известно также, что для каждого n существует граф на n вершинах, кликовое хроматическое число которого не меньше 
для некоторой константы c. Таким образом, между верхними и нижними оценками сохраняется зазор в корень из логарифма раз, и этот зазор кому-то предстоит устранить — возможно, кому-то из читающих эту брошюру!
Отметим и один из интереснейших классов графов. Это так называемые геометрические графы. У них вершины — точки в пространстве (или даже просто на плоскости), а ребра соединяют пары точек, находящихся на расстоянии не больше 1. Эти графы важны для таких классических задач комбинаторики, как проблема Нелсона-Хадвигера раскраски пространства, проблема Борсука и др. (см. брошюры А. М. Райгородского «Хроматические числа», «Проблема Борсука» (М.: МЦНМО, 2015); про разные вариации на тему этих графов уже бывали задачи на МMO — например, задача 6 для 10 класса в варианте 2010 года). Так вот для этих графов даже в случае плоскости зазор между верхними и нижними оценками аж от 3 до 9!