Двоичные немагические прямоугольники

Добрый день.

Начало нового месяца — это часто хороший повод порешать очередную задачку от команды IBM (год назад мы уже обращались к этому источнику). Предлагаю перевод декабрьского задания (или прочтите оригинал):

У двоичной матрицы NxM (т.е. в ячейках которой только нули и единицы) мы можем посчитать N сумм значений в строках и M сумм значений в столбцах. Эти суммы иногда могут однозначно задавать матрицу. Например, суммы [1,2,0][2,1] могут быть только у следующей матрицы:
     1 0
     1 1
     0 0

Но иногда суммы задают не одну матрицу. Например, суммы [1,1,2][2,2] соответствуют следующим двум матрицам:
     0 1     1 0
     1 0     0 1
     1 1     1 1

Декабрьское задание состоит в поиске таких сумм, которые описывают ровно 29 разных двоичных матриц. Чтобы исключить тривиальные решения, наложим ещё одно ограничение: матрица должна содержать не более 50 бит. В качестве решения принимаются две строки: в первой N целых чисел и во второй M целых чисел. Произведение N*M должно быть не больше 50.

Если вам интересен такой класс задачек, то давайте поделимся друг с другом в комментариях ответами на следующие вопросы:
1) Придумали ли вы тривиальное решение (более 50 бит, на которое намекают авторы задачи)?
2) Какие количества двоичных матриц вы умеете выражать преложенным способом (в условии задачи есть решения для 1 и 2, а спрашивается про 29, но ведь есть ещё много других чисел)?
3) Придумали ли вы способы «умножать» ранее найденное решение (т.е. получать наборы сумм, описывающих N*k матриц, имея решение для N матриц)?
4) Нашли ли вы решение для 29 матриц и небольшого их размера? Если да, то можете вписать своё имя на сайт IBM, отправив им своё решение (каждый месяц несколько десятков человек пользуются этой возможностью)

Хорошей недели и интересных задачек!