mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2014-12-02, 17:40   #1
Xyzzy
 
Xyzzy's Avatar
 
Aug 2002

2·4,153 Posts
Default December 2014

http://domino.research.ibm.com/Comm/...ember2014.html
Xyzzy is offline   Reply With Quote
Old 2014-12-02, 20:57   #2
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

22×3×5×23 Posts
Default

Quote:
Originally Posted by Xyzzy View Post
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++;
  }
}
alpertron is offline   Reply With Quote
Old 2014-12-02, 22:42   #3
TheMawn
 
TheMawn's Avatar
 
May 2013
East. Always East.

172710 Posts
Default

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.
TheMawn is offline   Reply With Quote
Old 2014-12-02, 23:00   #4
TheMawn
 
TheMawn's Avatar
 
May 2013
East. Always East.

11×157 Posts
Default

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.
TheMawn is offline   Reply With Quote
Old 2014-12-03, 02:31   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

Quote:
Originally Posted by TheMawn View Post
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
science_man_88 is offline   Reply With Quote
Old 2014-12-03, 12:20   #6
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

138010 Posts
Default

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
File Type: zip results.zip (4.7 KB, 139 views)
alpertron is offline   Reply With Quote
Old 2014-12-03, 12:22   #7
Drdmitry
 
Drdmitry's Avatar
 
Nov 2011

22·5·13 Posts
Default

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.
Drdmitry is offline   Reply With Quote
Old 2014-12-03, 12:30   #8
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

25448 Posts
Default

Do your 8 solutions cover all 1800 solutions found by my program?
alpertron is offline   Reply With Quote
Old 2014-12-03, 13:57   #9
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

22×3×5×23 Posts
Default

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
File Type: zip results46.zip (7.4 KB, 144 views)

Last fiddled with by alpertron on 2014-12-03 at 14:14
alpertron is offline   Reply With Quote
Old 2014-12-03, 14:14   #10
Drdmitry
 
Drdmitry's Avatar
 
Nov 2011

22·5·13 Posts
Default

Quote:
Originally Posted by Drdmitry View Post
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.
Drdmitry is offline   Reply With Quote
Old 2014-12-03, 14:14   #11
axn
 
axn's Avatar
 
Jun 2003

141916 Posts
Default

Quote:
Originally Posted by alpertron View Post
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
axn is offline   Reply With Quote
Reply

Thread Tools


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

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


Mon Oct 18 08:01:33 UTC 2021 up 87 days, 2:30, 0 users, load averages: 1.19, 1.06, 1.01

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.