17
$\begingroup$

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?

$\endgroup$
16
$\begingroup$

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$.

| improve this answer | |
$\endgroup$
  • $\begingroup$ The matrix approach is very nice here, very clear. $\endgroup$ – hexomino Aug 25 at 23:26
  • $\begingroup$ Nicely done. Can you give any intuition as to what the transpose trick translates into if we go back from the matrix abstraction to the original setting? $\endgroup$ – Paul Panzer Aug 25 at 23:44
  • $\begingroup$ @PaulPanzer Not sure if I can give a clear interpretation. It may be described like this: if we fill a number (positive or negative) in every cell, so that for each cell, the sum of this cell with its adjacent cells is zero, then the sum of all cells must be zero. This exactly comes from the fact that there is a filling giving "all $11$". On the other hand, this fact implies that if we have two different ways of filling the cells, such that the sums of any cell with its adjacent cells are the same in both fillings, then the sum of all cells in both fillings are the same. $\endgroup$ – WhatsUp Aug 26 at 3:45
  • 1
    $\begingroup$ @Aqua Of course I don't. In fact I'm also curious to see whether there is a simple way to explain the appearance of the number $11$. $\endgroup$ – WhatsUp Aug 26 at 13:29
  • 1
    $\begingroup$ very nice proof. One can also argue that if x represents the state of the board then the dot product of v * x is always divisible by 11. But the desired end state x = [2020,2020,...,2020] does not satisfy v * x is divisible by 11, contradiction. $\endgroup$ – happystar Aug 27 at 2:43
8
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Nicely done. You beat me to it - I was only able to analyse the simpler case of 3x3 instead of 5x5 and came to the same conclusion (i.e. no solution) $\endgroup$ – happystar Aug 26 at 22:34
4
$\begingroup$

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$.

| improve this answer | |
$\endgroup$
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$

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.