|
|
 |
Условие
Главная аудитория фирмы "Рога и копыта" представляет собой квадратный зал из восьми рядов по восемь мест. 64 сотрудника фирмы писали в этой аудитории тест, в котором было шесть вопросов с двумя вариантами ответа на каждый. Могло ли так оказаться, что среди наборов ответов сотрудников нет одинаковых, причем наборы ответов любых двух людей за соседними столами совпали не больше, чем в одном вопросе? (Столы называются соседними, если они стоят рядом в одном ряду или друг за другом в соседних рядах.)
Решение
Обозначим первый ответ на каждый вопрос через нуль, а второй – через единицу. Тогда каждому набору ответов соответствует набор из шести нулей и единиц. Аудиторию будем представлять в виде таблицы 8×8, в клетки которой расставляются наборы из шести цифр. Нам требуется заполнить таблицу так, чтобы соседние по вертикали или горизонтали наборы совпадали не более чем по одной цифре. Чётностью набора будем называть чётность суммы его цифр.
Покажем сначала, как заполнить клетки так, чтобы соседние наборы различались ровно по одной цифре. Пусть в наборах каждой строки последние три цифры одинаковы, а первые три определяются слева направо так: 000, 001, 011, 010, 110, 100, 101, 111. Тогда каждые два соседние по горизонтали набора различаются ровно по одной цифре. В каждом столбце последние три цифры определим таким же образом сверху вниз. Аналогично получится, что каждые два соседние по вертикали набора различаются ровно по одной цифре. Остается заметить, что все наборы различны, поскольку
наборы из разных столбцов отличаются в первых трёх цифрах, а из разных строк
– во вторых трёх.
Покрасим теперь все клетки таблицы в белый и чёрный цвета в шахматном порядке так, чтобы левая верхняя клетка была белой. Тогда все чётные наборы попадут в белые клетки, а все нечётные – в чёрные. В каждом наборе в чёрных клетках заменим единицы на нули, а нули – на единицы. Заметим, что при таком обращении чётность набора не изменится, поэтому по-прежнему во всех белых клетках будут чётные наборы, а во всех чёрных – нечётные. При этом все нечётные наборы будут попарно различаться (в противном случае какие-то два набора совпадали бы до обращения), аналогично все чётные будут попарно различаться. Значит, и все наборы будут различны. Наконец, каждые две соседние клетки имеют разные цвета, и, поскольку до обращения наборы
в них различались ровно по одной цифре, после обращения наборы будут совпадать ровно по одной цифре.
На рисунке показан пример аналогичной расстановки для квадрата 4×4.
Ответ
Могло.
