Ponder This Challenge - January 2014 - Boolean 21x6 matrix

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

Solution

• Click here to view the solution

  One can solve this problem by either encoding it as a CNF formula and using any SAT solver, or running backtracking from the bottom of the table T.

  Here are solutions for 21x6
  000000
  111111
  100000
  111110
  010000
  111100
  001001
  001110
  010100
  001101
  100100
  101101
  110101
  000111
  110111
  100011
  110011
  111011
  111010
  011010
  011000
  and for the bonus 33x7
  0000000
  1111111
  1000000
  1110111
  0100000
  1101111
  0000010
  1110011
  1101000
  0111011
  1001001
  0110001
  1000101
  0010001
  1011101
  0011000
  1011110
  1110000
  1010110
  1110100
  0011100
  0110101
  0001101
  0111101
  0101100
  0100111
  0101101
  0101111
  0101010
  1101011
  1101010
  1111010
  1111110

  The best solutions are
  2x1
  3x2
  5x3
  8x4
  13x5
  21x6

  Bonus question: Can you find a 34x7 solution and keep the Fibonacci sequence?

Solvers

• *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)