20141202, 17:40  #1 
"Mike"
Aug 2002
2^{2}×3×5×7×19 Posts 
December 2014

20141202, 20:57  #2  
Aug 2002
Buenos Aires, Argentina
2·11·61 Posts 
Quote:
The program in Visual Studio 98 is: Code:
#include <stdio.h> #include <stdlib.h> #include <string.h> int main(int argc, char *argv[]) { char oldstr[100]; char newstr[100]; int a,b,c,d,e,f,g,h,i,j; int count = 0; FILE *fpFile = fopen("test", "wt"); #if 0 for (a=0; a<1048576; a++) { b = ((a >> 19) & 1) + ((a >> 15) & 1) + ((a >> 11) & 1) + ((a >> 7) & 1) + ((a >> 3) & 1); c = ((a >> 18) & 1) + ((a >> 14) & 1) + ((a >> 10) & 1) + ((a >> 6) & 1) + ((a >> 2) & 1); d = ((a >> 17) & 1) + ((a >> 13) & 1) + ((a >> 9) & 1) + ((a >> 5) & 1) + ((a >> 1) & 1); e = ((a >> 16) & 1) + ((a >> 12) & 1) + ((a >> 8) & 1) + ((a >> 4) & 1) + (a & 1); f = ((a >> 19) & 1) + ((a >> 18) & 1) + ((a >> 17) & 1) + ((a >> 16) & 1); g = ((a >> 15) & 1) + ((a >> 14) & 1) + ((a >> 13) & 1) + ((a >> 12) & 1); h = ((a >> 11) & 1) + ((a >> 10) & 1) + ((a >> 9) & 1) + ((a >> 8) & 1); i = ((a >> 7) & 1) + ((a >> 6) & 1) + ((a >> 5) & 1) + ((a >> 4) & 1); j = ((a >> 3) & 1) + ((a >> 2) & 1) + ((a >> 1) & 1) + (a & 1); fprintf(fpFile, "[%d %d %d %d] [%d %d %d %d %d]\n",b,c,d,e,f,g,h,i,j); } #endif for (a=0; a<262144; a++) { b = ((a >> 17) & 1) + ((a >> 14) & 1) + ((a >> 11) & 1) + ((a >> 8) & 1) + ((a >> 5) & 1) + ((a >> 2) & 1); c = ((a >> 16) & 1) + ((a >> 13) & 1) + ((a >> 10) & 1) + ((a >> 7) & 1) + ((a >> 4) & 1) + ((a >> 1) & 1); d = ((a >> 15) & 1) + ((a >> 12) & 1) + ((a >> 9) & 1) + ((a >> 6) & 1) + ((a >> 3) & 1) + (a & 1); e = ((a >> 17) & 1) + ((a >> 16) & 1) + ((a >> 15) & 1); f = ((a >> 14) & 1) + ((a >> 13) & 1) + ((a >> 12) & 1); g = ((a >> 11) & 1) + ((a >> 10) & 1) + ((a >> 9) & 1); h = ((a >> 8) & 1) + ((a >> 7) & 1) + ((a >> 6) & 1); i = ((a >> 5) & 1) + ((a >> 4) & 1) + ((a >> 3) & 1); j = ((a >> 2) & 1) + ((a >> 1) & 1) + (a & 1); fprintf(fpFile, "[%d %d %d] [%d %d %d %d %d %d]\n",b,c,d,e,f,g,h,i,j); } fclose(fpFile); system("sort <test >test2"); fpFile = fopen("test2", "rt"); oldstr[0] = 0; while (!feof(fpFile)) { fgets(newstr, 100, fpFile); if (strcmp(newstr, oldstr)) { if (count == 29) { printf("%s", oldstr); } count = 0; strcpy(oldstr, newstr); } count++; } } 

20141202, 22:42  #3 
May 2013
East. Always East.
11·157 Posts 
It says to limit the search to matrices with 50 or less bits. 4x5 and 3x6 are but a fraction of all allowable matrices.
The biggest are 2x25 3x16 4x12 5x10 6x8 7x7 But there are still tens of others. 5x9, 5x8, 5x7, 5x6, etc.. I'm trying to think of a way to not bruteforce this problem, because a 7x7 matrix gives 2^{49} combinations to check. 
20141202, 23:00  #4 
May 2013
East. Always East.
11×157 Posts 
The first thing I see is that a matrix with any one row or column with all the same numbers is essentially equivalent to the same matrix, but without that row or column in it.
For example Code:
1 1 1 1 4 0 0 0 1 1 0 0 0 1 1 1 0 0 1 2 1 0 0 1 2 1 0 1 1 3 1 0 1 1 3 1 0 0 0 1 1 0 0 0 1 3 0 1 3 4 1 2 4 If you think about it, you could begin with a 2x2 matrix and work outward in any direction to reach any size you want, using the logic that adding a row or column of 1's or 0's would not grant any new solutions. If that is the case, then you can eliminate any matrices with rows or columns where the elements are all the same from your search, assuming you started from a smaller matrix. Again, just to make myself clear: A matrix of any size (for example, 5x4) which contains a row or column where all the elements are the same (for example a row of 1's) can be considered equivalent to that same matrix without the row or column (so a 4x4 matrix) because the sums are affected in a very predictable way. The row of 1's always has a sum of 4 and the sums of columns are always just 1 bigger, so any 5x4 matrix where the top row is all 1's will not give 29 identical sums if a 4x4 matrix (without the row of 1's) does not give 29 identical sums. Thus, if you very methodically checked all 3x6 matrices, then you can eliminate all 3x7 and 4x6 matrices with rows or columns with all the same element from your search. 
20141203, 02:31  #5  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
Quote:
I think I have a way to simplify it a bit but (I'm trying currently in my head only) which rows in says a n by m matrix are able to be moved to cover where the other one used to occupy ex: [1 0 1] < move one left [0,1,0] < one left as well result: [0 1 1] [1,0,0] because if I thought about it correctly it's a sum of the number of exchanges possible that has to add to 29. Last fiddled with by science_man_88 on 20141203 at 02:33 

20141203, 12:20  #6 
Aug 2002
Buenos Aires, Argentina
2×11×61 Posts 
I extended the program to handle 5x5 matrices as follows:
Code:
#include <stdio.h> #include <stdlib.h> #include <string.h> int main(int argc, char *argv[]) { char oldstr[100]; char newstr[100]; int a,b,c,d,e,f,g,h,i,j,k; int count = 0; FILE *fpFile = fopen("test", "wt"); for (a=0; a<33554432; a+=2) { b = ((a >> 24) & 1) + ((a >> 19) & 1) + ((a >> 14) & 1) + ((a >> 9) & 1) + ((a >> 4) & 1); c = ((a >> 23) & 1) + ((a >> 18) & 1) + ((a >> 13) & 1) + ((a >> 8) & 1) + ((a >> 3) & 1); d = ((a >> 22) & 1) + ((a >> 17) & 1) + ((a >> 12) & 1) + ((a >> 7) & 1) + ((a >> 2) & 1); e = ((a >> 21) & 1) + ((a >> 16) & 1) + ((a >> 11) & 1) + ((a >> 6) & 1) + ((a >> 1) & 1); f = ((a >> 20) & 1) + ((a >> 15) & 1) + ((a >> 10) & 1) + ((a >> 5) & 1); g = ((a >> 24) & 1) + ((a >> 23) & 1) + ((a >> 22) & 1) + ((a >> 21) & 1) + ((a >> 20) & 1); h = ((a >> 19) & 1) + ((a >> 18) & 1) + ((a >> 17) & 1) + ((a >> 16) & 1) + ((a >> 15) & 1); i = ((a >> 14) & 1) + ((a >> 13) & 1) + ((a >> 12) & 1) + ((a >> 11) & 1) + ((a >> 10) & 1); j = ((a >> 9) & 1) + ((a >> 8) & 1) + ((a >> 7) & 1) + ((a >> 6) & 1) + ((a >> 5) & 1); k = ((a >> 4) & 1) + ((a >> 3) & 1) + ((a >> 2) & 1) + ((a >> 1) & 1); fprintf(fpFile, "[%d %d %d %d %d] [%d %d %d %d %d]\n",b,c,d,e,f,g,h,i,j,k); fprintf(fpFile, "[%d %d %d %d %d] [%d %d %d %d %d]\n",b,c,d,e,f+1,g,h,i,j,k+1); } fclose(fpFile); system("sort test /O test2"); fpFile = fopen("test2", "rt"); oldstr[0] = 0; while (!feof(fpFile)) { fgets(newstr, 100, fpFile); if (strcmp(newstr, oldstr)) { if (count == 29) { printf("%s", oldstr); } count = 0; strcpy(oldstr, newstr); } count++; } } Obviously these 1800 solutions can be reduced by taking into account the permutations. 
20141203, 12:22  #7 
Nov 2011
3×79 Posts 
Some variation of dynamic programming will do the job.
I found 8 nonequivalent solutions (up to permutation of rows and columns and up to adding lines full of zeroes or ones). But if one notices that all of them go in pairs (one can flip all zeroes to ones and vice versa) then there are four nonequivalent solutions. 
20141203, 12:30  #8 
Aug 2002
Buenos Aires, Argentina
1342_{10} Posts 
Do your 8 solutions cover all 1800 solutions found by my program?

20141203, 13:57  #9 
Aug 2002
Buenos Aires, Argentina
2×11×61 Posts 
I'm attaching all 2880 solutions for the 4x6 binary matrix case.
I ran the program one more time, for 3x8 binary matrix, but it found no solutions. Last fiddled with by alpertron on 20141203 at 14:14 
20141203, 14:14  #10  
Nov 2011
3·79 Posts 
Quote:
I have looked at your result file. Up to permutations of rows and columns it actually contains two nonequivalent solutions. And up to flipping all zeroes to ones and vice versa there is essentially one solution there. 

20141203, 14:14  #11  
Jun 2003
2^{3}·607 Posts 
Quote:
Code:
[1 1 3 3 4] [1 1 3 3 4] [1 2 2 4 4] [1 2 2 4 4] EDIT: Same for 4x6 case Code:
[1 2 3 5] [1 1 1 2 3 3] [1 3 4 5] [1 1 2 3 3 3] Also, even the two unique solutions aren't unique!! They're obtained from each other by swapping 1's and 0's. So net effect, there is only one unique solution for each class! Last fiddled with by axn on 20141203 at 14:23 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
December 2017  Batalov  Puzzles  4  20180104 04:33 
December 2016  Xyzzy  Puzzles  11  20170124 12:27 
December 2015  Xyzzy  Puzzles  15  20160106 10:23 
Conference in Amsterdam 12 December  fivemack  Information & Answers  6  20111212 13:13 
Server update in December  ltd  Prime Sierpinski Project  4  20101217 13:14 