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

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.

***

 Records   |  Conjectures  |  Problems  |  Puzzles

 Home | Melancholia | Problems & Puzzles | References | News | Personal Page | Puzzlers | Search | Bulletin Board | Chat | Random Link Copyright © 1999-2012 primepuzzles.net. All rights reserved.