Ponder This

January 2014

<<December January February>>

Ponder This Challenge:

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.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

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

  

Challenge: 12/31/2013 @ 01:00 PM EST
Solution: 02/03/2014 @ 01:00 PM EST
List Updated: 01/31/2014 @ 01:00 PM EST

People who answered correctly:

*Oleg Vlasii (01/01/2014 12:16 PM EDT)
*Don Dodson (01/03/2014 09:08 AM EDT)
*Andrew Gacek (01/03/2014 03:57 PM EDT)
*William Gunther (01/04/2014 10:46 AM EDT)
Reiner Martin (01/04/2014 02:34 PM EDT)
Ziqi Zhu (01/05/2014 12:04 AM EDT)
*Cynthia Beauchemin (01/05/2014 12:12 AM EDT)
*José Eduardo Gaboardi de Carvalho (01/05/2014 05:36 PM EDT)
*Motty Porat (01/07/2014 09:39 AM EDT)
Joseph DeVincentis (01/07/2014 11:53 AM EDT)
*Olivier Mercier (01/07/2014 04:39 PM EDT)
*Igor Novak (01/07/2014 05:32 PM EDT)
Craig Milhiser (01/07/2014 07:34 PM EDT)
Peter Gerritson (01/08/2014 02:57 PM EDT)
Brian Kell (01/08/2014 07:52 PM EDT)
Tao Liu (01/10/2014 11:39 PMEDT)
Peter C. Shim (01/11/2014 08:14 AM EDT)
Hakan Summakoglu (01/11/2014 10:32 AM EDT)
Katherine Oh (01/11/2014 10:42 AM EDT)
Renato Negrinho (01/12/2014 04:22 AM EDT)
William Kang (01/12/2014 08:03 AM EDT)
Jaesung Son (01/12/2014 09:03 AM EDT)
David Yang (01/12/2014 12:39 PM EDT)
Stéphane Higueret (01/13/2014 09:37 AM EDT)
Rajendran Thirupugalsamy (01/14/2014 02:44 AM EDT)
Alok Menghrajani (01/16/2014 03:38 PM EDT)
*Gilles-Philippe Paillé (01/18/2014 09:02 PM EDT)
Todd Will (01/21/2014 08:12 AM EDT)
Seongwoo Hong (01/22/2014 05:21 PM EDT)
Clive Tong (01/23/2014 01:16 AM EDT)
Daniel Bitin (01/23/2014 10:14 AM EDT)
Liubing Yu (01/23/2014 03:00 PM EDT)
David Greer (01/24/2014 09:05 AM EDT)
Boaz Menuhin (01/26/2014 04:25 AM EDT)
Keith B. Hermiz (01/29/2014 08:29 PM EDT)
Romain Hollanders, Balázs Gerencsér & Raphaël Jungers (01/31/2014 09:56 AM EDT)
Masoud Alipour (01/31/2014 02:26 PM EDT)
Mauro Bampo (01/31/2014 04:03 PM EDT)
Philipp Seemann (02/01/2014 03:42 PM EDT)
Armin Krauss (02/03/2014 04:59 PM EDT)

Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.