5
$\begingroup$

Inspired by Board with all 2020s :

Zeroes are written in all cells of a n×n board. We can take an arbitrary cell and increase by 1 the number in this cell and all cells having a common side with it.

  • Is there a highest n for which an equal positive number can be reached in all cells simultaneously?
  • Is there a highest n for which an equal positive number can not be reached in all cells simultaneously?

Note: It is possible for n = 1,2,4 and 5. It is not possible for n=3 and n=6

My LP solver tells me under 100 it is solvable for

n = 1,2,4,5,8,9,10,14,15,19,20,22,24,25,29,32,34,39,44,59,64,71,76,77,82,84,94,97 (I do not see a pattern)

Obviously at least 1 of the answers is no. But are there an infinite number of solvable and an infinite number on unsolvable sizes, or has one of the types a finite number of sizes? (I don't know myself)*

Hint: impossibility for specific cases can be proven mathematically:

- If a balanced matrix with only positive increment values exists, then a fully symmetric balanced matrix with only positive increment values can be constructed from it by adding mirror images. Hence: If no fully symmetric balanced matrix with only positive increment values exists, the case is infeasible

- Looking at increments for fully symmetric n = 3: - Corner total: T = 2*side+corner - Side total: T = 2*corner+centre+side - Centre total: T = centre+4*side Eliminating side and corner from these equations yields centre = -Total/7 -> infeasible

- I applied the same technique to prove n=6 is infeasible

It seems likely that if, with size, the number of equations increases, the chance of a negative value increases. However, there might a a pattern or redundant equation might appear, making (some, or all) high n cases feasible.

$\endgroup$
0
4
$\begingroup$

PARTIAL ANSWER:

Let us say a matrix is balanced if any cell plus its neighbours adds up to the same constant. This implies it is possible for n = 1,2,4,5 because each number tells us how many times we need to apply the +1 operation. With n = 3,6, we run into trouble because we need to apply the +1 operation a negative number of times. Hence the balanced matrix is useless. Note this does not prove the impossibility of n=3 or 6 since there might be a different balanced matrix which does work. But it gives us reason to suspect it's not possible. I believe what is required is a systematic method of generating balanced matrices for all n.enter image description here

NOTE: Credit belongs to WhatsUp for finding the balanced matrix for n = 5 in the original Board with all 2020s problem.

$\endgroup$
2
$\begingroup$

Silly answer:

If you make zero presses then all cells will be equal and remain at zero. This means that it works for any $n$. To avoid this problem you must state that at least one press must be made.

$\endgroup$
1
  • $\begingroup$ I don't think zero is a "positive number" as asked for in the question. $\endgroup$ – Retudin Sep 11 '20 at 13:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.