IBM Research | Ponder This | January 2014 challenges
Skip to main content

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 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

  

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 webmaster.