Задача 66489

Тема:    [ Теория алгоритмов (прочее) ]

Сложность: 6 Классы: 8,9,10,11

Условие

Авторы: Бородин П.А., Канунников А.Л.

В доме из $2^n$ комнат сделали евроремонт. При этом выключатели света оказались перепутанными, так что при включении выключателя в одной комнате загорается лампочка, вообще говоря, в какой-то другой комнате. Чтобы узнать, какой выключатель к какой комнате подсоединён, прораб посылает несколько людей в какие-то комнаты, чтобы те, одновременно включив там выключатели, вернулись и сообщили ему, горела лампочка в их комнате или нет.
а) Докажите, что за $2n$ таких посылок прораб может установить соответствие между выключателями и комнатами.
б) А может ли он обойтись $2n-1$ такими посылками?

Решение

а) Занумеруем все комнаты наборами длины $n$ из нулей и единиц (числами от 0 до $2^n-1$ в двоичной системе). Обозначим через $A_k$ и $B_k$ множества наборов, у которых на $k$-м месте стоит соответственно 1 или 0. Для каждого $k=1,\dots,n$ множества $A_k$ и $B_k$ не пересекаются и вместе составляют всё множество наборов.

Рассмотрим следующий алгоритм посылок: в $(2k-1)$-й раз прораб посылает людей в комнаты с номерами из множества $A_k$, в $(2k)$-й раз он посылает людей в комнаты с номерами из множества $B_k$, $k$ меняется от 1 до $n$. Всего получается $2n$ посылок.

Пусть лампочка в комнате с номером $i$ включается выключателем в комнате с номером $f(i)$. Если $i \in A_k$ и во время $(2k-1)$-й посылки лампочка в $i$-й комнате включилась, то $f(i)\in A_k$, а если не включилась, то $f(i)\in B_k$. Аналогично, если $i \in B_k$ и во время $(2k)$-й посылки лампочка в $i$-й комнате включилась, то $f(i)\in B_k$, а если не включилась, то $f(i)\in A_k$. Таким образом, за $(2k-1)$-ю и $(2k)$-ю посылки прораб точно устанавливает $k$-й разряд номера $f(i)$ для каждого $i$. Следовательно, после $2n$ указанных посылок он полностью установит соответствие $f$.

б) Покажем, что за $2n-1$ посылок прораб также может установить соответствие $f$.

Пусть первые $2n-2$ посылки те же, что в предыдущем пункте. После них прораб для каждого $i$ знает номер $f(i)$ с точностью до последнего знака. Построим специальный граф, соответствующий этому знанию. Вершины графа располагаются в два горизонтальных ряда, каждый из которых соответствует парам $P_1, P_2, \dots, P_{2^{n-1}}$ наборов (номеров комнат), различающихся только в последнем знаке (например, $P_1=\{0\dots0, 0\dots01\}$). Рёбра графа проходят только от вершин верхнего ряда к вершинам нижнего ряда по следующему правилу: вершина в верхнем ряду, соответствующая паре $P_s$, соединена с вершиной в нижнем ряду, соответствующей паре $P_t$, в точности тогда, когда для некоторого $i\in P_s$ прорабу известно, что $f(i)\in P_t$.

В таком графе все вершины имеют степень 2. Следовательно, он разбивается на непересекающиеся циклы, в которых все вершины и рёбра проходятся ровно по одному разу. Зафиксируем для каждого из этих циклов обход, начинающийся в вершине верхнего ряда, и рассмотрим все нечётные ребра во всех этих обходах. Каждое из этих рёбер порождено соответствием $i\to f(i)$ в указанном выше смысле. Прораб отбирает множество $A$ всех номеров $i$, соответствующих выбранным нечетным рёбрам, и в $(2n-1)$-й раз посылает людей в комнаты с этими номерами (их $2^{n-1}$ штук).

Покажем, что в результате он полностью установит соответствие $f$.

Пусть $i\in A$ и известно, что $f(i)\in P_j$. В множестве $A$ есть ровно один номер $m$ из пары $P_j$. Если во время $(2n-1)$-й посылки лампочка в $i$-й комнате загорелась (выключатель в $m$-й комнате включается), то $f(i)=m$, в противном случае $f(i)$ есть номер, дополнительный к $m$ в паре $P_j$.

Пусть $i\notin A$ и известно, что $f(i)\in P_j$. В множестве $A$ есть такой номер $q$, что $f(q)$ тоже лежит в $P_j$. Во время $(2n-1)$-й посылки, как уже было сказано, номер $f(q)$ устанавливается, и тогда $f(i)$ есть номер, дополнительный к $f(q)$ в паре $P_j$.

Комментарий.

Авторам неизвестно минимальное количество посылок, необходимое для установления соответствия между комнатами и выключателями.

Ответ

б) Да, может.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	81
Год	2018
класс
Класс	11
задача
Номер	6