mersenneforum.org December 2014
 Register FAQ Search Today's Posts Mark Forums Read

 2014-12-02, 17:40 #1 Xyzzy     "Mike" Aug 2002 816910 Posts December 2014
2014-12-02, 20:57   #2
alpertron

Aug 2002
Buenos Aires, Argentina

135610 Posts

Quote:
 Originally Posted by Xyzzy http://domino.research.ibm.com/Comm/...ember2014.html
I've made a fast approach by computing all binary matrix combinations of 4x5 and 3x6, sorting them and then count the repeated results. In no case there are 29 occurrences. It appears that the matrix must have a different size.

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++;
}
}

 2014-12-02, 22:42 #3 TheMawn     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 brute-force this problem, because a 7x7 matrix gives 249 combinations to check.
 2014-12-02, 23:00 #4 TheMawn     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 Note that adding the top row of 1's had no bearing on the sums of all the other rows and only increased each column sum by 1. If you couldn't find 29 identical sums in a 4x4 matrix, any 5x4 with a row of 1's or 0's and any 4x5 matrix with a column of 1's or 0's will also not give you 29 identical sums, because the sums are "equivalent" in that sense. 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.
2014-12-03, 02:31   #5
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by TheMawn I'm trying to think of a way to not brute-force this problem, because a 7x7 matrix gives 249 combinations to check.
Hint:

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 2014-12-03 at 02:33

2014-12-03, 12:20   #6
alpertron

Aug 2002
Buenos Aires, Argentina

22·3·113 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++;
}
}
I attached the solutions found by the program.

Obviously these 1800 solutions can be reduced by taking into account the permutations.
Attached Files
 results.zip (4.7 KB, 102 views)

 2014-12-03, 12:22 #7 Drdmitry     Nov 2011 111100102 Posts Some variation of dynamic programming will do the job. I found 8 non-equivalent 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 non-equivalent solutions.
 2014-12-03, 12:30 #8 alpertron     Aug 2002 Buenos Aires, Argentina 22·3·113 Posts Do your 8 solutions cover all 1800 solutions found by my program?
2014-12-03, 13:57   #9
alpertron

Aug 2002
Buenos Aires, Argentina

22·3·113 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.
Attached Files
 results46.zip (7.4 KB, 107 views)

Last fiddled with by alpertron on 2014-12-03 at 14:14

2014-12-03, 14:14   #10
Drdmitry

Nov 2011

2·112 Posts

Quote:
 Originally Posted by Drdmitry Some variation of dynamic programming will do the job. I found 8 non-equivalent 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 non-equivalent solutions.
I computed only 3 * n (n <= 16) and 4 * n (n <= 12) cases, so my solutions do not cover that in result file.
I have looked at your result file. Up to permutations of rows and columns it actually contains two non-equivalent solutions. And up to flipping all zeroes to ones and vice versa there is essentially one solution there.

2014-12-03, 14:14   #11
axn

Jun 2003

136A16 Posts

Quote:
 Originally Posted by alpertron Do your 8 solutions cover all 1800 solutions found by my program?
I see only two unique solutions to the 5x5 case (in the results file):
Code:
[1 1 3 3 4] [1 1 3 3 4]
[1 2 2 4 4] [1 2 2 4 4]
Everything else is a permutation: 30 permutations for each row x 30 permutations for each column x 2 sets = 1800.

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]
24 perm x 60 perm x 2 sets = 2880

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 2014-12-03 at 14:23

 Similar Threads Thread Thread Starter Forum Replies Last Post Batalov Puzzles 4 2018-01-04 04:33 Xyzzy Puzzles 11 2017-01-24 12:27 Xyzzy Puzzles 15 2016-01-06 10:23 fivemack Information & Answers 6 2011-12-12 13:13 ltd Prime Sierpinski Project 4 2010-12-17 13:14

All times are UTC. The time now is 01:40.

Wed May 19 01:40:19 UTC 2021 up 40 days, 20:21, 0 users, load averages: 2.15, 2.27, 2.17