Имеется прямоугольная таблица размером M × N, заполненная числами 0 и 1, обладающая следующими свойствами. Во‐первых, в каждой строке и в каждом столбце есть хотя бы один элемент, равный 1. Во‐вторых, нет ни одной пары одинаковых строк, а также ни одной пары одинаковых столбцов. Таблицы, обладающие этими свойствами, назовем «хорошими».
Две таблицы назовем эквивалентными в том и только в том случае, если из одной из них можно получить другую путем перестановки строк и/или столбцов. Приведем пример двух эквивалентных таблиц размером 3 × 3.
|
|
Вторая таблица получается из первой сначала перестановкой в ней 1‐й и 3‐й строк, потом 2‐го и 3‐го столбца в полученной таблице, а затем 1‐й и 2‐й строки в последней полученной таблице.
а) Сколько существует различных попарно неэквивалентных «хороших» таблиц размером 2 × 3?
б) Укажите количество всех таблиц, эквивалентных «хорошей» таблице
| 1 | 1 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
в) Какое максимальное число столбцов может быть в «хорошей» таблице, содержащей М строк?
а) В столбцах могут стоять либо две единицы, либо единица и нуль (двумя способами). Порядок столбцов не важен, важно лишь их количество. Значит, единственная возможная таблица без одинаковых столбцов имеет вид, приведенный ниже.
| 1 | 1 | 0 |
| 1 | 0 | 1 |
б) При всех перестановках в каждой строке и каждом столбце окажется ровно один нуль. Есть ровно 6 вариантов расставить в таблице три нуля так, чтобы никакие два не попали в один ряд (и заполнить остальные клетки единицами). Нетрудно убедиться, что все эти шесть вариантов можно реализовать перестановкой строк.
в) Всего есть 2M вариантов заполнения столбца нулями и единицами, один из которых состоит лишь из нулей. Поэтому столбцов не более чем 2M − 1. Очевидно, если взять каждый из них в одном экземпляре, то все столбцы будут различны. Все строки также будут различны, поскольку для любых двух строк найдется столбец, в котором на пересечении с этими строками стоят разные цифры.
Ответ: а) 1, б) 6, в) 2M − 1.