IBM Ponder This #189 · January 2014

This month's challenge is from Thomas Dueholm Hansen and Uri Zwick (thanks).
Find a matrix of bits T which has 6 columns and at least 21 rows such that the following holds:

1. For every row 1<=i_1<21 there exists a column j such that T(i_1,j) != T(i_1+1,j) and T(i_1+1,j) = T(21,j)

2. For every pair of rows 1<=i_1< i_2<21 there exists a column j such that T(i_1,j) != T(i_1+1,j) and T(i_1+1,j) = T(i_2,j) = T(i_2+1,j).

Here is an example of a solution for the same problem with an 8 x 4 matrix:

0011
1101
1010
1100
0110
0100
0000
0001

Bonus question: Find this type of matrix with 7 columns and at least 33 rows.

Solution

Best opened after a real attempt

To be added.