Problems & Puzzles: Puzzles

Puzzle 772. Entry 1363 by Claudio Meller This is another extension to a puzzle from Claudio Meller, that corresponds to the entry 1363 of his always interesting pages. There, Claudio asks you to fill a NxN matrix A with distinct non-negative integers such that you will form a second NxN matrix B the following way: Each cell in B is the sum of the corresponding value of the cell in A plus the values of all the neighboring cells in A too.   Example:   A -> B 1 2 3 12 21 16 4 5 6 27 45 33 7 8 9 24 39 28   Both matrixes A & B are valid if all the integers are distinct. Claudio asks for solutions where the sum of the integers in B is minimal. In a second question he asks that the integers values in B must be prime numbers as much as possible, keeping the same minimal sum condition than before. Carlos Rivera sent the following solution for N=3, with the minimal sum and the maximal quantity of primes in B.   A -> B sum=304 qty of primes=8 5 9 13 17 31 23 3 0 1 43 64 41 15 11 7 29 37 19   Q1. Send your minimal sum, maximal quantity of primes for N=3, 4, 5 & 6.   Carlos Rivera also extended this same puzzle asking for the most prime integers in both matrixes, A & B and minimal sum in B. This is his best result for N=3: 16 primes in both matrixes; minimal sum in B = 484   A qty of primes=8 -> B sum=484 qty of primes=8 3 11 23 31 67 47 17 0 13 43 98 71 7 5 19 29 61 37 Q2. Send your maximal quantity of primes in both A & B, and minimal sum in B, for N=3, 4, 5 & 6.

---

Contribution came from Emmanuel Vantieghem.

	Question Q1
	N=3					sum	309
	A						B
0	4	10				11	23	17
6	1	2				41	61	43
12	18	8				37	47	29
							all prime
	N=4					sum	988
7	6	12	5			17	43	59	53
4	0	14	22			29	71	97	89
10	2	16	20			41	79	109	83
1	24	8	3			37	61	73	47
							all prime
	N=5					sum	2353
2	6	3	9	12		13	23	37	53	43
1	4	7	8	14		31	41	61	83	73
5	13	0	11	19		71	101	103	109	79
28	20	23	17	10		107	167	163	157	97
15	26	37	16	24		89	149	139	127	67
							all prime
	Question Q2
	N=3					sum	546
7	3	19				17	59	47
5	2	23				41	112	89
11	13	29				31	83	67
	9 primes						8 primes
	N=4					sum 1728
29	11	7	43			59	71	89	78
19	0	5	23			113	127	107	83
41	13	2	3			137	181	131	101
47	17	37	31			118	157	103	73
	15 primes						14 primes
	N=5					sum 4479
8	5	11	2	47		23	53	71	139	109
7	3	19	31	29		73	103	101	229	199
37	13	0	17	73		107	149	151	239	197
43	4	23	41	6		223	307	271	353	269
67	59	61	53	79		173	257	241	263	179
	21 primes						25 primes

***

Carlos Rivera started a private-follow-up with some of the puzzlers related to this puzzle. I started asking for a regular approach of assignament of odd numbers in the Matrix A nxn in order to guarantee to get exactly nxn odd numbers in Matrix B.

The result of this rich discussion was that:

a) for any n=>2 always exist an arrangement of odd integers in matrix A such that in matrix B you get nxn odd integers.

b) There is a regular approach in order to set at least one matrix A arrangement for any kind of n>2 value.
As a matter of fact there are three distinct approaches, one for each case: n=3k, n=3k+1 and n=3k+2.
See sketches below (E = Even integer; O = Odd integer):

n=3k

n=3

n=6

n=9

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

O

E

E

O

E

E

O

E

E

O

E

E

O

E

E

O

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

O

E

E

O

E

E

O

E

E

O

E

E

O

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

O

E

E

O

E

E

O

E

E

E

E

E

E

E

E

E

E

n=3k+1

n=4

n=7

n=10

O

E

E

O

O

E

E

O

E

E

O

O

E

E

O

E

E

O

E

E

O

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

O

E

E

O

O

E

E

O

E

E

O

O

E

E

O

E

E

O

E

E

O

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

O

E

E

O

E

E

O

O

E

E

O

E

E

O

E

E

O

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

O

E

E

O

E

E

O

E

E

O

n=3k+2

n=5

n=8

n=11

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

O

E

E

O

E

O

E

E

O

E

E

O

E

O

E

E

O

E

E

O

E

E

O

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

O

E

E

O

E

O

E

E

O

E

E

O

E

O

E

E

O

E

E

O

E

E

O

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

O

E

E

O

E

E

O

E

O

E

E

O

E

E

O

E

E

O

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

E

O

E

E

O

E

E

O

E

E

O

BTW, for n=3k and n=3k+1, the assignament for the matrix A is unique (the already shown in matrixes above).

But for n=3k+2, there are 2^(2n-1) distinct possible assignaments; nevertheless, the assignament using a minimal of odd integers is the already shown above.

***

Later W. Edwin Clark discovered more issues around this follow-up

2. It appears that there is always at least one solution.  I was going to leave this as a question

but I happened to dig up a paper I read in 1989 that gives this as a corollary of a more

general result. Namely, one can replace the n x n grid graph by any finite simple graph. See

 

  Klaus Sutner, "Linear Cellular Automata and the Garden-of-Eden", Mathematical

  Intelligencer Vol 11, No. 2 1989.

3. If you interpret our situation in terms of cellular  automata, as in Sutner's paper,  the question is whether or not there is a global state which leads to the all 1's state.  That is, is the all 1's state a "garden-of-Eden" state -- one with no predecessor. 

(His answer is no.)

4. So our sequence a(n) is the number of predecessors of the

all one's state of the cellular automaton on the n x n grid

graph with edges joining diagonal neighbors as well as vertical

and horizontal neighbors, whose local rule is f(i,j) = sum of the state at vertex

(i,j) and the states at all of its neighbors mod 2. 

producing a OEIS sequence...and things became a kind of very complex for me... :-)

***

Emmanuel wrote this (Jan 30, 2015)

I made a Mathematica program that confirms all values of a(n) found by Edwin.

I just used basic Linear Algebra.  For every  n  I constructed the  (n^2)x(n^2) matrix AA of the equations that have to be solved and the matrix AC = AA with an extra column of  n^2 'ones'.

If both matrices have the same rank u, then the system of equations has a solution.  The number of solutions then is precisely  2^(n^2 - u).

Mathematica computes these values in less than one minute.

I'm allmost sure that Edwin's conjecture about  a(n)  is true and that it is provable.

***

W. Edwin Clark sent the following last comment to this puzzle (Feb 4, 2015)

The sequence related to our discussion has finally been approved and published. It is http://oeis.org/A254460.

Emmanuel, you might want to put in your Mathematica program.

***