Задание 19 из ЕГЭ по математике (профиль): задача 44
Имеется прямоугольная таблица размером $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$ человек стоят по кругу, все они разного возраста. Каждый сказал: «Я старше обоих своих соседей». а) Могло ли оказаться так, что все сказали правду? б) Могло ли оказаться так, чт…
Множество чисел, состоящее не меньше чем из трёх элементов, назовём «правильным», если его можно разбить на два непустых подмножества с одинаковым произведением чисел. Если какое-т…
Тридцать пять шариков массой $1$ г, $2$ г, $…$, $35$ г разложили по двум коробкам, в каждой коробке хотя бы один шарик. Масса каждого шарика выражается целым числом граммов. Затем из второ…
