Board with all 2020s

Question

Zeroes are written in all cells of a $5 \times 5$ 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 it possible to obtain the number 2020 in all cells simultaneously?

Answer 1

It is

not possible.

Reasoning:

Let $M$ be the $25 \times 25$ matrix representing the adjacent relations among the cells. We are thus looking for a (column) vector $x$ of $25$ non-negative integers such that $Mx$ is the vector $[2020, 2020, \dots, 2020]$. (I will use $[]$ to denote column vectors and $()$ to denote row vectors.)

We first note that $M$ is a symmetric matrix.
Moreover, the following table shows that there is a (column) vector $v = [1,5,4,2,4,\dots, 4,5,1,2,7]$ such that $Mv =[11, 11, \dots, 11]$.
1, 5, 4, 2, 4
5, 1, 0, 1, 5
4, 0, 5, 3, 1
2, 1, 3, 1, 2
4, 5, 1, 2, 7

Since $M$ is symmetric, this means that there is a (row) vector $w( = \frac1 {11} v^T)$ such that $wM = (1, 1, \dots, 1)$.
Furthermore, we calculate the sum of entries in $v$ and get $69$, which is not divisible by $11$.

To conclude, assume that we have a vector $x$ such that $Mx = [2020, \dots, 2020]$.
We then have $M(x - \frac{2020}{11}v) = 0$, which implies $wM(x - \frac{2020}{11}v) = 0$.
This gives $(1, \dots, 1)x = \frac{2020}{11}(1, \dots, 1)v = \frac{2020}{11}\cdot 69$, which is not an integer. Therefore $x$ cannot be an integral vector.

In conclusion, if we want all the numbers to become a given number $n$, then it is possible to do so if and only if $n$ is a multiple of $11$.

Answer 2

A less technical solution:

We can (try to) make a symmetric solution that makes all numbers equal (where the 6 variables signify how often a cell is chosen):

abcba  
bdedb  
cefec  
bdedb  
abcba  

For the total we get: T = a+2b = a+b+c+d = 2b+c+e = 2b+d+2e = 2d+c+e+f = 4e+f

From which we can extract equalities:

(1+3) a = c+e
(1+2) b = c+d
(3+4) c = d+e
(5+6) 3e = c+2d
(4+6) f = 2b+d-2e = 5d

Any positive integer solution of this must be a multiple of f=10, d=2 etc, leading to a total that is a multiple of 22.

Any asymmetric solution can be made symmetrical by adding up all 8 (horizontal vertical and diagonal) reflections so 8 times any solution must lead to a multiple of 22. Thus any single solution leads to a multiple of 11. 2020 is not a multiple of 11.

Answer 3

Neater solution, as requested by OP:

Let $A$ be a constant matrix [1,5,4,2,4;5,1,0,1,5;4,0,5,3,1;2,1,3,1,2;4,5,1,2,7] and $B$ be any obtainable board state such as [1,1,1,0,0;0,1,0,0,0;0,0,0,2,0;0,0,2,2,2;0,0,0,2,0]. Then the "dot product" $\sum_{ij} A_{ij}B_{ij}$ is always a multiple of 11. But the desired state is $B^* = 2020 \times 1_{5\times5}$ where $1_{5\times 5}$ represents the matrix of all ones. But the dot product of $A$ and $B^*$ is not a multiple of 11, contradiction.

Most of the credit belongs to @WhatsUp for finding the matrix $A$.

Answer 4

This is just an "elementarization" of @WhatsUp's elegant proof to help in giving some intuition.

Let there be two patterns of $n_i$ moves, respectively, each summing to a uniform increase of $k_i$ in each square. Let $\{x_{ij}\}$ the "cell count", i.e. the number of times square $j$ was chosen (as the center) in pattern $i$. Now multiply each cell count in pattern $1$ by each cell count in pattern $2$ that is within the "+"-pento centered at the first cell (this is, of course, symmteric, i.e., equivalently, the first cell is within the pento centered at the second cell) and form the sum: $S = \sum_{j,j' \text{"pento-connected"}} x_{1j}x_{2j'}$. Then $S = \sum_j x_{1j} \sum_{j\text{within pento at}j'} x_{2j'} = \sum_j x_{1j} k_2 = 25 k_2 n_1$ and, similarly, $S = 25 k_1 n_2$.

Substituting $k_1,n_1 = 11,69$ from pattern given by WhatsUp and $k_2 = 2020$ we find that a matching integer $n_2$ does not exist.

Answer 5

Here is the closest to an intuitive argument I could muster explaining the numbers $69,11$. Here intuitive means not involving any systems of equations that couldn't be solved on sight. Whether it means truly illuminating or interesting is another matter...

Divide the board into three groups each comprising two subgroups: $$\begin{matrix}a&A&b&A&a\\A&B&C&B&A\\b&C&c&C&b\\A&B&C&B&A\\a&A&b&A&a\end{matrix}$$. We will heavily abuse notation and let $a$, say, reference the subgroup, its total occupancy or the class of moves that are centered (up to natural $8$-fold symmetry) at the square.

Now observe that up to $8$-fold symmetry for each of the subgroups $a,b,c$ there is only one move that inncreases its average compared to $A,B,C$, respectively, viz. $A,b,C$. Therefore each move that increases the balance in favor of $A,B,C$ vs $a,b,c$, respectively, must be balanced by the appropriate number of steps $A,b,C$, respectively.

There is some cascading: Starting with an imbalance $B>b$ of $1$ this must be balanced by one $b$ move causing a new imbalance $A>a$---which can be remedied without further side-effects---and a new imbalance $C>c$ of $1$. A $C>c$ imbalance can only be balanced by a $C$ move which reblances in steps of $3$ (in $C$ units, $3/4$ in $c$ units, difference due to group sizes). but reintroduces a $B>b$ imbalance of $1$. If we combine all this we find that fully balancing an $A>a$ of $1$ cost $1A$, a $B>b$ of $2$ cost $1C,3b,3A$, and a $C>c$ of $2$ cost $1C,1b,1A$.

Once the groups are balanced the absolute levels of groups $Aa$ and $Cc$ can be upward corrected as needed using moves $a$ and $c$. In particular, these moves are neutral in terms of within-group balance. Note that we have touched all moves except $B$ now, and every move was neutral or cascaded into a small letter group net win. To formalize this weight $A:1,C:1,B:4$. Then every move except $B$ is neutral or moves the weighted sum of the within group balance towards small letter favored. Therefore any balanced pattern can be built by choosing a total amount of $B's$ which must be even and then balancing them. The imbalance caused by two $B$'S is $B>b:2,C>c:4,A>a:4$: Fixing balance requires $14A,5b,3C$. Together with $2B$ this leads to occupancy $B=b=22$ which is not divisible by the group size $4$ so we have to double all numbers. To bring the group sizes $A=a$ and $C=c$ to the correct levels we find we have to add $5C$ and $16a$ leading to a total of $69$.

This argument is almost constructive up to theoretically feasible within subgroup imbalance. But we start with four $B$'s of our choosing, so everything with the possible exception of $A$ (Which has $8$ members can be built symmetrically.