В парламент выбрано 256 депутатов. Каждый из них ответил на 8 вопросов анкеты (требующих ответов «да» или «нет») и выяснилось, что никакие двое не ответили одинаково на все вопросы. Можно ли их рассадить на 256 стульев, расставленных в квадрате $16\times16$ так, чтобы ответы каждого отличались от ответа любого его соседа (слева, справа, сзади, спереди):
Начнём с задачи а). Заметим, что всего существует $256=2^8$ различных «номеров» длиной 8 из 0 и 1, т. е. 256 наборов ответов «да» или «нет» на 8 вопросов. Таким образом, мы должны указать такое взаимно однозначное соответствие между этими номерами (от $00\ldots0$ до $11\ldots1$) и 256 стульями, что соседние стулья имеют номера, отличающиеся лишь в одном разряде.
Поступим так. Пусть первые четыре цифры номера зависят только от того, в каком столбце, а последние четыре — от того, в какой строке таблицы $16\times16$, изображающей стулья, мы находимся. Как именно — ясно из рисунка (цифры с пятой по восьмую выбираются аналогично по вертикали).
Легко проверить, что номера соседей отличаются лишь в одном разряде.
Заметим, что сюжет этой задачи возник вовсе не из политических размышлений, а из одной конкретной проблемы современной молекулярной биологии. Известно, как много сил, времени, да и денег тратят учёные на расшифровку длинных последовательностей ДНК — «слов» из четырёх букв $A$, $C$, $G$, $T$ (обозначающих нуклеотиды). И вот несколько лет назад ряд учёных (почти одновременно в США, России и других странах) предложили попробовать автоматизировать процесс расшифровки так. В каждую миниатюрную клеточку матрицы $N\times N$ помещается некоторое «слово» длиной, скажем, 8 из четырёх букв (поскольку $4^8=2^{16}=2^8\times2^8$, матрица должна содержать $256\times256$ клеточек); при определённых условиях к данной клеточке будет прилипать только такой отрезок ДНК из раствора, который содержит соответствующее (комплиментарное) слово из 8 букв $A$, $C$, $G$, $T$. Для не слишком длинного (порядка тысячи нуклеотидов) куска ДНК по этим данным — зная, какие слова длиной 8 он содержит, — с некоторой точностью его можно восстановить. (Это — отдельная тема, которую мы надеемся когда-нибудь обсудить. Сейчас весь этот проект при поддержке нескольких ведущих медицинских фирм проходит стадию первых попыток реального воплощения.) Но, как всегда, при «прилипании» и «сканировании» матрицы с целью выявления занятых клеточек возможны ошибки. Поэтому важно, чтобы близкие клеточки занимали очень похожие слова. Отсюда и наша задача а).
Что касается б), то она сводится к а) с помощью шахматной раскраски таблицы $16\times16$. Заметим, что у каждого номера $X$ из 0 и 1 есть его «антипод» $\overline{X}$ — номер, полученный заменой всех 0 на 1 и 1 на 0. Если номер $B$ отличается от номера $A$ в одном разряде, то $\overline{B}$ от $A$ отличается в 7 разрядах. Поэтому для построения примера б) достаточно номера всех белых клеток оставить такими, какими они были в а), а в чёрных заменить антиподами.
Разумеется, та же конструкция годится и для таблиц $2^k\times2^k$ при любом натуральном $k$.
