На конференцию приехали несколько человек. Докажите, что их можно разместить в двух конференц-залах так, чтобы у каждого из них в своем зале имелось четное число знакомых (один из залов можно оставить пустым).
Проведем решение индукцией по количеству участников конференции. База индукции проверяется непосредственно.
Предположим, что для n участников утверждение задачи верно.
Пусть на конференцию приехали n + 1 участников. Если каждый из них имеет четное число знакомых, что можно оставить одну из комнат пустой и требование задачи будет выполнено. Поэтому будем считать, что некоторый участник А имеет нечётное количество знакомых B1, B2, …, B2k + 1. Попросим участника A на время удалиться с конференции. Кроме того, заставим любых двух его знакомых познакомиться между собой, если они прежде не были знакомы, и, напротив, временно прервать знакомство, если они знали друг друга. Полученную компанию из n человек можно, по предположению индукции, разместить в двух комнатах так, чтобы у каждого было четное число знакомых в своей комнате. Не умаляя общности, можно считать, что участники B1, B2, …, B2s попали в первую комнату, а B2s + 1, B2s + 2, …, B2k + 1 — во вторую (
). Теперь позовем обратно изгнанного A и подселим его в первую комнату — он будет знать
там четное число людей. При этом количество знакомых у участников B1, B2, …, B2s станет нечетным. Наконец, вернем все знакомства между Bi (
) в первоначальное состояние. Каждое приобретенное или потерянное знакомство меняет количество знакомых на единицу. Поэтому у каждого из B1, B2, …, B2s количество знакомых среди людей этого набора поменяет четность (и станет четным), а у каждого из B2s + 1, B2s + 2, …, B2k + 1 по-прежнему останется четным. У других участников, кроме A и Bi, наборы знакомых всё это время вообще не менялись. Поэтому полученное размещение всех участников по двум комнатам удовлетворяет условию задачи.