Ponder This Challenge - December 2014 - A matrix with 29 solutions

Ponder This Challenge:

Given an NxM binary matrix, we can compute the N sums of the rows and the M sums of the columns . These sums can sometimes uniquely define the matrix. For example, the sums [1,2,0][2,1] can be generated only from the matrix

1 0
1 1
0 0

But sometimes there are several options. For example [1,1,2][2,2] can be generated from two matrices:

0 1    1 0
1 0    0 1
1 1    1 1

The challenge this month is to find sums that are generated from exactly 29 different binary matrices.

To rule out trivial solution, we further require that each matrix have no more than 50 bits.

Please provide your answer as two lines, the first line with N integers and the second with M integers. N*M should be no more than 50.

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

  The trivial solution for any number N is [1,1,1,...,1][1,N-1], which gives a 56-bit matrix in our case (N=29). To disallow this solution, we required that the matrix have no more than 50 bits.

  The second systematic way is [M-1,1,1,1,...,1][N-1,1,1,1,...,1], which generates 1+(N-1)*(M-1) matrices. This gives solutions like [7,1,1,1,1][4,1,1,1,1,1,1,1].

  Gyorgy Gyomai sent us another way to generate a set of numbers: [M-1,2,1][2,2,1,1,1,...,1], which gives 3*k-4 different generating matrices, giving the solution [10,2,1],[2,2,1,1,1,1,1,1,1,1,1].

  The smallest solution (24 bits) is [1,2,3,5],[1,1,1,2,3,3].

Solvers

• Dan Dima (11/28/2014 06:14 PM EDT)
• David Brink & Claus Andersen (11/28/2014 08:00 PM EDT)
• Radu-Alexandru Todor (11/28/2014 09:41 PM EDT)
• James Dow Allen (11/29/2014 10:01 AM EDT)
• Oleg Vlasii (11/29/2014 11:05 AM EDT)
• Martin Thiim (11/29/2014 09:30 PM EDT)
• Tobias Zurell (11/30/2014 12:58 AM EDT)
• Anatoli Plotnikov (11/30/2014 07:43 PM EDT)
• Andreas Stiller (11/30/2014 08:34 PM EDT)
• YanwuHe (12/01/2014 09:17 AM EDT)
• Alex Fleischer (12/01/2014 02:16 PM EDT)
• David Dodson & Don Dodson (12/01/2014 02:40 PM EDT)
• Cynthia Beauchemin (12/01/2014 03:15 PM EDT)
• Daniel Bitin (12/01/2014 03:37 PM EDT)
• Reiner Martin (12/01/2014 07:50 PM EDT)
• Florian Fischer (12/01/2014 08:15 PM EDT)
• Thomas Fleming (12/01/2014 10:32 PM EDT)
• Shirish Chinchalkar (12/02/2014 10:27 AM EDT)
• AthenaHealth Math Club (12/02/2014 03:49 PM EDT)
• Hakan Summakoğlu (12/02/2014 05:22 PM EDT)
• Hendrik Nigul (12/02/2014 05:26 PM EDT)
• Thomas Slothouber (12/02/2014 05:26 PM EDT)
• Alan Murray (12/02/2014 07:48 PM EDT)
• Bruce Norskog (12/02/2014 09:14 PM EDT)
• Dmitry Bodyagin (12/03/2014 08:54 AM EDT)
• Darío Alpern (12/03/2014 11:01 AM EDT)
• Sergey Koposov (12/03/2014 02:04 PM EDT)
• Alex P. (12/03/2014 02:09 PM EDT)
• Cody Pfau (12/03/2014 03:52 PM EDT)
• Graham Hemsley (12/03/2014 04:08 PM EDT)
• Dennis Langdeau (12/03/2014 05:49 PM EDT)
• Peter Gerritson (12/03/2014 08:06 PM EDT)
• Christian Pietsch (12/03/2014 08:47 PM EDT)
• Amos Guler (12/04/2014 06:11 AM EDT)
• José Eduardo Gaboardi de Carvalho (12/04/2014 01:59 PM EDT)
• Dan Ismailescu (12/04/2014 03:06 PM EDT)
• Elia Chinellato1 (12/04/2014 03:41 PM EDT)
• Victor Chang (12/04/2014 05:00 PM EDT)
• Fletcher Dostie (12/04/2014 07:47 PM EDT)
• Motty Porat (12/04/2014 09:22 PM EDT)
• Deron Stewart (12/05/2014 03:58 AM EDT)
• Harald Bögeholz (12/05/2014 11:44 AM EDT)
• Adam Daire (12/05/2014 09:17 PM EDT)
• Liubing Yu (12/05/2014 09:19 PM EDT)
• Lee Gao (12/06/2014 02:14 AM EDT)
• John Tromp (12/06/2014 08:27 PM EDT)
• Colin Bell (12/07/2014 05:37 AM EDT)
• Vladimir Dorofeev (12/08/2014 08:38 AM EDT)
• Lorenz Reichel (12/08/2014 06:15 PM EDT)
• Kristiyan Ivanov (12/08/2014 09:58 PM EDT)
• Saeed Sarfjoo (12/09/2014 12:03 AM EDT)
• Igor Novak (12/09/2014 01:09 AM EDT)
• Kang Jin Cho (12/09/2014 08:54 AM EDT)
• Robert Gauss (12/09/2014 02:46 PM EDT)
• János Kramár (12/09/2014 05:58 PM EDT)
• Pål Hermunn (12/10/2014 09:09 AM EDT)
• David Greer (12/11/2014 07:39 PM EDT)
• Rachit Srivastava (12/11/2014 07:57 PM EDT)
• Gilles-Philippe Paillé (12/11/2014 10:28 PM EDT)
• Hyung Sik Hwang (12/11/2014 11:37 PM EDT)
• Ariel Ish-Shalom (12/12/2014 07:29 AM EDT)
• Joseph Berman (12/12/2014 05:06 PM EDT)
• William Heller (12/15/2014 12:24 AM EDT)
• Tamir Ganor & Shouky Dan (12/15/2014 11:54 AM EDT)
• Michael Schuresko (12/15/2014 02:14 PM EDT)
• Chanakarn Chinchatchawal (12/15/2014 02:42 PM EDT)
• Govind A. N. (12/16/2014 07:58 AM EDT)
• Armin Krauss (12/16/2014 10:14 AM EDT)
• Sri Mallikarjun J. (12/16/2014 12:42 PM EDT)
• Bryce Herdt (12/16/2014 02:56 PM EDT)
• Adrian Orzepowski (17/12/2014 16:12 EDT)
• Michel Hannoyer (17/12/2014 16:54 EDT)
• Ji Eun (Grace) Kim (12/20/2014 03:58 PM EDT)
• Peter C. Shim (12/20/2014 04:30 PM EDT)
• Yujin Kim (12/20/2014 05:38 PM EDT)
• Jhiseung Daniel Hahn (12/20/2014 05:46 PM EDT)
• Robert Sarvis (12/20/2014 07:22 PM EDT)
• Gyorgy Gyomai (12/20/2014 08:42 PM EDT)
• Hyun Jae Moon (12/21/2014 02:03 AM EDT)
• James Ha (12/21/2014 06:39 PM EDT)
• Denys Kopiychenko (12/21/2014 08:01 PM EDT)
• Gyozo Nagy (12/21/2014 11:51 PM EDT)
• Philip Kinlen (12/23/2014 09:25 PM EDT)
• Kwonil Kobe Ko (12/30/2014 04:07 AM EDT)
• Huafeng Jiang (12/30/2014 12:53 PM EDT)
• Vincent Park (12/24/2014 03:50 PM EDT)
• Chris Shannon (12/24/2014 08:26 PM EDT)
• Yooree Ha (12/24/2014 09:00 PM EDT)
• Hyun Min Victoria Woo (12/24/2014 10:51 PM EDT)
• Moinca & Khalil (12/25/2014 08:58 AM EDT)
• Boris Rakus (12/25/2014 05:03 PM EDT)
• Fabio Filatrella (12/25/2014 08:01 PM EDT)
• Sergey Grishaev (12/25/2014 10:27 PM EDT)
• David Yang (12/26/2014 01:18 AM EDT)
• SeongKweon Hong (12/26/2014 12:23 AM EDT)
• Mathias Schenker (12/27/2014 11:51 AM EDT)
• Ilya Persky (12/27/2014 07:40 PM EDT)
• Anders Bisbjerg Madsen (12/27/2014 07:42 PM EDT)
• Colas Kerkhove (12/27/2014 07:48 PM EDT)
• Lee Jongyeob (12/28/2014 03:12 PM EDT)
• Seung Hwan (Sonny) An (12/28/2014 05:30 PM EDT)
• Fabio Michele Negroni (12/29/2014 03:12 AM EDT)
• Chisato Hasegawa (12/31/2014 10:06 AM EDT)
• Louis P. Slothouber (12/30/2014 04:46 PM EDT)
• William Kang (12/31/2014 05:40 PM EDT)
• Li Li (02/01/2015 00:19 AM EDT)
• Todd Will (12/31/2014 04:01 PM EDT)