Problems & Puzzles: Puzzles

Puzzle 316. Divide a square of primes.

One more puzzle inspired in another from the many times cited book from N. Yoshigahara, 'Puzzles 101'. This time from his Puzzle 58.

Our problem goes this way:

Allocate orderly the first n2 primes on a grid size nxn. Then divide the grid in just two (2) polygons so that the sum of the primes in each area is the same  number

Example for n=5, sum = 530:

2

3

5

7

11

13

17

19

23

29

31

37

41

43

47

53

59

61

67

71

73

79

83

89

97

(BTW, I have found zero solutions for n=3 and 20 distinct solutions for n=5.)

Question: Found ALL the solutions for n=5.

 

Giovanni Resta solved this puzzle. He also exposes his very interesting computational approach.

Himself and Anurag Sahay explored other variations of the same puzzle.

Giovanni Resta wrote:

I found 20 solution for the case 5x5, so they are the same you already found.

I have also examined the cases 4x4, 6x6.and 7x7.

Since the sum of the first 16 or 36 prime numbers is odd, we can't have solution.

However, I considered two variants.

1) first 16 (or 36) prime numbers to be divided in two sets whose sums differs by 1 i.e. 190 and 191 (1213 and 1214).

In the 4x4 case we have 5 solutions:
0 0 0 0
0 0 1 0
0 0 1 0
0 1 1 1
--------
1 1 1 1
1 0 0 1
1 0 1 1
0 0 0 1
--------
0 0 0 0
0 0 0 0
0 1 1 0
1 1 1 0
---------
1 1 1 1
1 0 0 1
1 0 0 1
1 1 0 0
---------
0 0 0 0
1 1 0 0
1 1 1 0
1 1 0 0


In the 6x6 case there are exactly 1294 distinct solutions, like:
1 1 1 1 1 1
1 1 1 1 1 1
1 0 0 1 1 1
1 1 0 1 1 1
1 1 0 1 1 0
0 0 0 0 0 0

2) the first 16 (36) ODD prime numbers.
The sum is even so the problem is well posed.
In the 4x4 case (sum 219) we have 3 solutions,.i.e:

1 1 1 1
0 1 0 1
0 0 0 1
0 0 1 1
--------
0 1 1 1
0 1 1 1
0 0 1 1
0 0 0 1
--------
1 1 1 0
1 0 1 0
1 0 0 0
1 1 1 0

In the case 6x6 (sum 1291) we have 809 solutions, like
1 1 1 1 1 1
1 1 1 1 0 1
1 1 1 1 0 1
1 1 1 1 0 1
1 1 1 1 0 0
0 0 0 0 0 0
--------------------------

For the 7x7 case (sum 2444) we have 87411 solutions, one being

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

I have solved the cases 4x4, 5x5 and 6x6 by brute force, enumerating all the possible 0-1 matrices (with one entry fixed) so respectively
2^15 = 32,768
2^24 = 16,777,216
2^35 = 34,359,738,368
For each matrix I have considered the sums of the two components, and if they matched I have checked if the two component were indeed two polygons.

For the case 7x7 this simple approach was infeasible, since
2^48 = 281,474,976,710,656
so I used a different method.

I wrote a very simple program that recursively construct all the partitions of the 7x7 matrix in two polygons such that one does not surround completely the other. This assumption greatly simplify my program and I've checked (by adding the numbers), that there cannot be a solution in which one of the polygons contains all the "border" and thus include the other polygon.
In practice, the program builds all the possible paths, between two points on the border, that divides the squares in two components.
Given a path is then quite easy to decide which little square belongs to which polygon.
Then, for every configuration I simply checked if the sums matched.
Just for the record, if we want the the sum of the SQUARES of the primes are equal then there are 31 solutions, one being:

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

and if we require that the sums of CUBES match then we have only 5 solutions, as

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

***

Anurag wrote:

One can ask another question: divide the square into m polygons whose areas are distinct primes and sum of the contents of each polygon is a distinct prime .
Obviously , (a) there must be a polygon of area =2 , if the square contains the first n^2 primes.
Else , (b) if the square has first n^2 odd primes, the least n with a solution is 4.

For (a) , I found these results:
For n=3, there is no solution.

There are 6 solutions for n=4(all of them with 3 polygons of areas 2,3,11).Primes in different polygons separated by comma(if there are m polygons,I am showing m-1 polygons for each solution):
1. 2 3 , 41 29 43
2. 2 3, 37 47 53
3. 2 3, 29 31 47
4. 2 11, 13 17 31
5. 2 11, 13 17 29
6. 2 11 , 5 7 19

For n=5 , there are many solutions with 4 polygons of areas 2,3,7,13.

1. 2 3, 53 59 37, 41 61 73 79 83 89 97
2. 2 3, 17 19 5, 7 11 23 29 43 47 67
3. 2 3, 7 11 29, 5 19 17 13 31 53 73
4. 2 3, 83 89 97,23 19 17 13 31 53 73
Can you find the other solutions for n=5.

If the areas of the polygons need not be distinct , I am showing 2 solutions for n=5: one has 8 polygons of areas 2(2 3), 3(5 7 11), 3(19 23 29), 3(13 17 31),
3(37 41 61) , 3(47 43 67), 3(71 97 89),5(53 59 73 79 83).
and the other with 4 polygons: 2(2 3), 5(37 41 61 59 53), 5(73 79 83 89 97) , 13(31 13 17 19 5 7 11 23 29
43 47 67 71).

For (b) , there are 4 solutions for n=4:
2 polygons of areas 3 and 13 .
1. 7 11 19
2. 13 29 43
3. 19 23 37
4. 31 47 29

***

 

 

 
     
Records   |  Conjectures  |  Problems  |  Puzzles