Имеется прямоугольная таблица размером $M×N$, заполненная числами 0 и 1, обладающ…
Имеется прямоугольная таблица размером $M×N$, заполненная числами 0 и 1, обладающая следующими свойствами. Во-первых, в каждой строке и в каждом столбце есть хотя бы один элемент, равный 1. Вовторых, нет ни одной пары одинаковых строк, а также ни одной пары одинаковых столбцов. Таблицы, обладающие этими свойствами, назовём хорошими.
Две таблицы назовём эквивалентными в том (и только том) случае, если из одной из них можно получить другую путём перестановки строк и/или столбцов. Приведём пример двух эквивалентных таблиц размером $3×3$.
| 1 | 1 | 1 |
| 1 | 1 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 0 | 0 | 1 |
| 1 | 1 | 1 |
Вторая таблица получается из первой сначала перестановкой в ней 1-й и 3-й строк, потом 2-го и 3-го столбца в полученной таблице и, наконец, 1-й и 2-й строки в последней полученной таблице.
а) Сколько существует различных попарно неэквивалентных хороших таблиц размером $2×2$?
б) Укажите количество всех таблиц, эквивалентных "хорошей" таблице.
| 1 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 |
в) 1. Какое минимальное число строк может быть в "хорошей" таблице, содержащей N столбцов?
2. Приведите пример "хорошей" таблицы, содержащей 4 столбца и минимально возможное число строк в ней (в ответе укажите таблицу, которая содержит максимальное число единиц, и её столбцы запишите по убыванию десятичных чисел, соответствующих этим столбцам и рассматриваемых как числа в двоичной системе с расположением цифр сверху вниз).
Объект авторского права ООО «Легион»
Вместе с этой задачей также решают:
$10$ человек стоят по кругу, все они разного возраста. Каждый сказал: «Я старше обоих своих соседей». а) Могло ли оказаться так, что все сказали правду? б) Могло ли оказаться так, чт…
Учитель задумал несколько различных целых чисел и выписал набор этих чисел и все их возможные суммы (по 2, по 3 и т.д. слагаемых) на доске в порядке неубывания. Например, если бы о…
На доске выписаны числа $7$ и $9$. За один ход выписанные числа $a$ и $b$ нужно заменить числами $(a+b-1)$ и $(2b+4)$. Например, из чисел $7$ и $9$ можно получить либо числа $15$ и $18$, либо числа $15$ …
