Задача М1286‍‍

Докажем по индукции более общее утверждение — про $2n$‍‍ делегатов и $n$‍‍ двухместных номеров, $n\ge2$‍.‍

Естественно изображать ситуацию в виде графа — системы точек (изображающих делегатов), некоторые пары которых соединены ребром (а именно, те пары делегатов, которые могут разговаривать друг с другом).

Для 4-х делегатов ($n=2$‍)‍ утверждение проверяется некоторым перебором. Если 1, 2, 3, 4 — делегаты (вершины графа), из которых каждый может поговорить хоть с одним из остальных, но при этом их нельзя поселить в двух двухместных номерах с соблюдением условий (т. е. в графе отсутствует одно из рёбер 12 или 34, а также одно из рёбер 13 или 24 и ребро 14 или 23), то остаётся возможным лишь случай, соответствующий графу, состоящему из трёх рёбер, выходящих из одной вершины (см. рисунок), что противоречит условию.

Переход от $n$‍‍ к $n+1$‍‍ очевиден. Предположим, что для $2n$‍‍ делегатов утверждение доказано, и докажем его для $2n+2$‍.‍ Можно выбрать любую пару из них, знающую общий язык, и поселить в один номер. А остальных $2n$‍‍ делегатов, по предположению индукции, можно расселить в $n$‍‍ номерах в соответствии с условием задачи.