Ponder This: January’s Challenge!

Are you a professional problem solver? If so, we invite you to submit your “Ponder This” solution for this month’s challenge. Ponder This is IBM Research’s monthly brain-twister where you can match wits with some of the best minds at IBM.

Ponder This Challenge:

This month’s challenge is from Thomas Dueholm Hansen and Uri Zwick (thanks).
Find a matrix of bits T which has at least 21 rows and 6 columns 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 at least 33 rows and 7 columns.

________

IBM Research will post the names of those who submit a correct, original solution to their website! If you don’t want your name posted then please include such a statement in your submission. Send your submission to the webmaster.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: webmster@us.ibm.com

Comments

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s