Consider a $2018 \times 2019$ board with integers in each unit square. Two unit squares are said to be neighbours if they share a common edge. In each turn, you choose some unit squares. Then for each chosen unit square the average of all its neighbours is calculated. Finally, after these calculations are done, the number in each chosen unit square is replaced by the corresponding average. Is it always possible to make the numbers in all squares become the same after finitely many turns?
Problem
Source: APMO 2019 P4
Tags: combinatorics, APMO
MarkBcc168
11.06.2019 03:38
This problem is extremely tricky. Here is the official solution.
The answer is $\boxed{\text{NO}}$. Consider the following table.
\begin{tabular}{||c|c|c||c|c|c||c|c|c|c||}
\hline
\hline
3 & 1 & 3 & 3 & 1 & 3 & $\cdots$ & 3 & 1 & 3 \\
\hline
0 & 2 & 0 & 0 & 2 & 0 & $\cdots$ & 0 & 2 & 0\\
\hline
\hline
0 & 2 & 0 & 0 & 2 & 0 & $\cdots$ & 0 & 2 & 0\\
\hline
3 & 1 & 3 & 3 & 1 & 3 & $\cdots$ & 3 & 1 & 3\\
\hline
\hline
3 & 1 & 3 & 3 & 1 & 3 & $\cdots$ & 3 & 1 & 3\\
\hline
0 & 2 & 0 & 0 & 2 & 0 & $\cdots$ & 0 & 2 & 0\\
\hline
\hline
0 & 2 & 0 & 0 & 2 & 0 & $\cdots$ & 0 & 2 & 0\\
\hline
3 & 1 & 3 & 3 & 1 & 3 & $\cdots$ & 3 & 1 & 3\\
\hline
\hline
$\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\ddots$ & $\vdots$ & $\vdots$ & $\vdots$ \\
\hline
3 & 1 & 3 & 3 & 1 & 3 & $\cdots$ & 3 & 1 & 3\\
\hline
0 & 2 & 0 & 0 & 2 & 0 & $\cdots$ & 0 & 2 & 0\\
\hline
\hline
\end{tabular}
We will consider this table in modulo $5$ soon but we have to overcome some technicalities first. At any point, the denominator of each entry is in form $2^a\cdot 3^b$, which is not divisible by $5$. Hence we can take $\frac{a}{b}\equiv ab^{-1}\pmod 5$ where $b^{-1}$ be the inverse of $b$ in modulo $5$.
It's straightforward to verify that if we move at any cells, the cell preserve its value in modulo $5$. So, we can't make all cells have same value in modulo $5$ and we are done.
USJL
11.06.2019 05:14
Proposed by YaWNeeT and me Submitting a troll problem to APMO has always been my dream...(X
It is known to us that if 2018 times 2019 is replaced by $m$ times $n$ where 2 or 3 divides $m$ and $(m,n)\neq (2,2)$ then the answer is still no. The same method works besides that one needs to take modulo $p$ for appropriate choices of $p$, depending on $m$ and $n$. We would be interested in any result beyond this or any alternative solution to the original problem.
GorgonMathDota
11.06.2019 06:10
USJL wrote: Proposed by YaWNeeT and me Submitting a troll problem to APMO has always been my dream...(X
It is known to us that if 2018 times 2019 is replaced by $m$ times $n$ where 2 or 3 divides $m$ and $(m,n)\neq (2,2)$ then the answer is still no. The same method works besides that one needs to take modulo $p$ for appropriate choices of $p$, depending on $m$ and $n$. We would be interested in any result beyond this or any alternative solution to the original problem.
Can I ask how did you come up with this problem?
skt
11.06.2019 12:55
I somehow managed to stumble upon the following observation without solving the original question. Apparently it would've given rise to a unique score on this question at the APMO (it's worth 3 marks according to the marking scheme):
The construction
$0$ $0$ $4$ $0$ $0$
$0$ $1$ $2$ $1$ $0$
$4$ $2$ $2$ $2$ $4$
$0$ $1$ $2$ $1$ $0$
$0$ $0$ $4$ $0$ $0$
proves that the answer is no when $5$ divides $m, n$ (all integers taken mod $5$, as in the official solution).
Functional
11.06.2019 13:25
skt wrote: I somehow managed to stumble upon the following observation without solving the original question. Apparently it would've given rise to a unique score on this question at the APMO (it's worth 3 marks according to the marking scheme):
The construction
$0$ $0$ $4$ $0$ $0$
$0$ $1$ $2$ $1$ $0$
$4$ $2$ $2$ $2$ $4$
$0$ $1$ $2$ $1$ $0$
$0$ $0$ $4$ $0$ $0$
proves that the answer is no when $5$ divides $m, n$ (all integers taken mod $5$, as in the official solution).
Can you share some details about the marking scheme?
USJL
11.06.2019 15:08
GorgonMathDota wrote: USJL wrote: Proposed by YaWNeeT and me Submitting a troll problem to APMO has always been my dream...(X
It is known to us that if 2018 times 2019 is replaced by $m$ times $n$ where 2 or 3 divides $m$ and $(m,n)\neq (2,2)$ then the answer is still no. The same method works besides that one needs to take modulo $p$ for appropriate choices of $p$, depending on $m$ and $n$. We would be interested in any result beyond this or any alternative solution to the original problem.
Can I ask how did you come up with this problem? YaWNeeT is the one who came up with the problem. He began with $1$ times $n$, and with some really simple argument he managed to show that the answer is no if and only if $n\geq 5$ (try it yourself!). He then asked me if it is possible to say anything for $m$ times $n$ when $m,n>2$. He wasn't able to think about the problem right away since he was in the hot spring when coming up with this problem(X) so I just took over and came up with the $2$ times $3$ and $2$ times $4$ construction. Then he realized that one could copy and paste the construction to get any $2s$ times $3t$ construction. skt wrote: I somehow managed to stumble upon the following observation without solving the original question. Apparently it would've given rise to a unique score on this question at the APMO (it's worth 3 marks according to the marking scheme):
The construction
$0$ $0$ $4$ $0$ $0$
$0$ $1$ $2$ $1$ $0$
$4$ $2$ $2$ $2$ $4$
$0$ $1$ $2$ $1$ $0$
$0$ $0$ $4$ $0$ $0$
proves that the answer is no when $5$ divides $m, n$ (all integers taken mod $5$, as in the official solution).
Whoa this is cool..... I would like to see a 3 tbh we totally thought that it was nearly impossible to get anything that is not 0 and 7 lol
RAMUGAUSS
11.06.2019 16:39
MarkBcc168 wrote: This problem is extremely tricky. Here is the official solution.
The answer is $\boxed{\text{NO}}$. Consider the following table.
\begin{tabular}{||c|c|c||c|c|c||c|c|c|c||}
\hline
\hline
3 & 1 & 3 & 3 & 1 & 3 & $\cdots$ & 3 & 1 & 3 \\
\hline
0 & 2 & 0 & 0 & 2 & 0 & $\cdots$ & 0 & 2 & 0\\
\hline
\hline
0 & 2 & 0 & 0 & 2 & 0 & $\cdots$ & 0 & 2 & 0\\
\hline
3 & 1 & 3 & 3 & 1 & 3 & $\cdots$ & 3 & 1 & 3\\
\hline
\hline
3 & 1 & 3 & 3 & 1 & 3 & $\cdots$ & 3 & 1 & 3\\
\hline
0 & 2 & 0 & 0 & 2 & 0 & $\cdots$ & 0 & 2 & 0\\
\hline
\hline
0 & 2 & 0 & 0 & 2 & 0 & $\cdots$ & 0 & 2 & 0\\
\hline
3 & 1 & 3 & 3 & 1 & 3 & $\cdots$ & 3 & 1 & 3\\
\hline
\hline
$\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\ddots$ & $\vdots$ & $\vdots$ & $\vdots$ \\
\hline
3 & 1 & 3 & 3 & 1 & 3 & $\cdots$ & 3 & 1 & 3\\
\hline
0 & 2 & 0 & 0 & 2 & 0 & $\cdots$ & 0 & 2 & 0\\
\hline
\hline
\end{tabular}
We will consider this table in modulo $5$ soon but we have to overcome some technicalities first. At any point, the denominator of each entry is in form $2^a\cdot 3^b$, which is not divisible by $5$. Hence we can take $\frac{a}{b}\equiv ab^{-1}\pmod 5$ where $b^{-1}$ be the inverse of $b$ in modulo $5$.
It's straightforward to verify that if we move at any cells, the cell preserve its value in modulo $5$. So, we can't make all cells have same value in modulo $5$ and we are done.
is there any other solution in a detailed manner.
pieater314159
12.06.2019 01:03
USJL wrote: Proposed by YaWNeeT and me Submitting a troll problem to APMO has always been my dream...(X
It is known to us that if 2018 times 2019 is replaced by $m$ times $n$ where 2 or 3 divides $m$ and $(m,n)\neq (2,2)$ then the answer is still no. The same method works besides that one needs to take modulo $p$ for appropriate choices of $p$, depending on $m$ and $n$. We would be interested in any result beyond this or any alternative solution to the original problem.
The details on this need a good bit of ironing out, but it should generalize a good bit.
By Kirchhoff's Tree Theorem, the number of spanning trees in a graph with vertex set $V$ is equal to $1/|V|$ times the product of the nonzero eigenvalues of its Laplacian matrix.
An array of values will be fixed by any allowable operation if and only if it is an eigenvector of the Laplacian matrix with eigenvalue $0$. In particular, if we can find some prime $p$ that divides the number of spanning trees of the graph determined by adjacency on an $m$ by $n$ grid, there is a nontrivial zero eigenvalue of that Laplacian matrix $\mod p$, and as such there's a vector linearly independent with the all-ones vector that is fixed by any allowable operation. However, because you can divide by $2$, $3$, or $4$ (because there are vertices with degrees $2$, $3$, and $4$), we need to specify that $p$ is not $2$ or $3$.
As such, it won't be possible as long as the number of spanning trees is not $2^a3^b$. In particular, the number of spanning trees on a $2\times 3$ grid is $15$, so $p=5$ should work. (I believe this technically gives a nonconstructive solution to the problem, since one can explicitly enumerate the spanning trees if one wishes, but best not.) One can find the number of spanning trees on an $m\times n$ grid here, which seems to support the claim that as long as $m,n>1$ and $(m,n)\neq (2,2)$, it's not possible.
I haven't been able to prove this (i.e. that it's never $2^a3^b$ except for the aforementioned cases), but on that page, it says that the number of spanning trees of an $m\times n$ grid is
$$\mathrm{Res}\left(U_{n-1}\left(\frac{x}{2}\right),U_{m-1}\left(\frac{4-x}{2}\right)\right),$$
where $\mathrm{Res}$ is the resultant, and $U(n,x)$ is the $n$th Chebyshev polynomial of the second kind. So, we just need to find a prime $p$ modulo which these have a common root. This seems doable...
YaWNeeT
12.06.2019 05:11
USJL wrote: YaWNeeT is the one who came up with the problem. He began with $1$ times $n$, and with some really simple argument he managed to show that the answer is no if and only if $n\geq 5$ (try it yourself!). He then asked me if it is possible to say anything for $m$ times $n$ when $m,n>2$. He wasn't able to think about the problem right away since he was in the hot spring when coming up with this problem(X) so I just took over and came up with the $2$ times $3$ and $2$ times $4$ construction. Then he realized that one could copy and paste the construction to get any $2s$ times $3t$ construction. Actually, in the very first version, one can only take average of one grid each time. However, after figuring out the invariant solution, we decided to make the operation more general.
USJL
15.06.2019 10:24
pieater314159 wrote: USJL wrote: Proposed by YaWNeeT and me Submitting a troll problem to APMO has always been my dream...(X
It is known to us that if 2018 times 2019 is replaced by $m$ times $n$ where 2 or 3 divides $m$ and $(m,n)\neq (2,2)$ then the answer is still no. The same method works besides that one needs to take modulo $p$ for appropriate choices of $p$, depending on $m$ and $n$. We would be interested in any result beyond this or any alternative solution to the original problem.
The details on this need a good bit of ironing out, but it should generalize a good bit.
By Kirchhoff's Tree Theorem, the number of spanning trees in a graph with vertex set $V$ is equal to $1/|V|$ times the product of the nonzero eigenvalues of its Laplacian matrix.
An array of values will be fixed by any allowable operation if and only if it is an eigenvector of the Laplacian matrix with eigenvalue $0$. In particular, if we can find some prime $p$ that divides the number of spanning trees of the graph determined by adjacency on an $m$ by $n$ grid, there is a nontrivial zero eigenvalue of that Laplacian matrix $\mod p$, and as such there's a vector linearly independent with the all-ones vector that is fixed by any allowable operation. However, because you can divide by $2$, $3$, or $4$ (because there are vertices with degrees $2$, $3$, and $4$), we need to specify that $p$ is not $2$ or $3$.
As such, it won't be possible as long as the number of spanning trees is not $2^a3^b$. In particular, the number of spanning trees on a $2\times 3$ grid is $15$, so $p=5$ should work. (I believe this technically gives a nonconstructive solution to the problem, since one can explicitly enumerate the spanning trees if one wishes, but best not.) One can find the number of spanning trees on an $m\times n$ grid here, which seems to support the claim that as long as $m,n>1$ and $(m,n)\neq (2,2)$, it's not possible.
I haven't been able to prove this (i.e. that it's never $2^a3^b$ except for the aforementioned cases), but on that page, it says that the number of spanning trees of an $m\times n$ grid is
$$\mathrm{Res}\left(U_{n-1}\left(\frac{x}{2}\right),U_{m-1}\left(\frac{4-x}{2}\right)\right),$$
where $\mathrm{Res}$ is the resultant, and $U(n,x)$ is the $n$th Chebyshev polynomial of the second kind. So, we just need to find a prime $p$ modulo which these have a common root. This seems doable...
This direction looks cool! I haven't thought about it in this way and will give it a shot once I have some time
USJL
15.06.2019 22:42
USJL wrote: pieater314159 wrote: USJL wrote: Proposed by YaWNeeT and me Submitting a troll problem to APMO has always been my dream...(X
It is known to us that if 2018 times 2019 is replaced by $m$ times $n$ where 2 or 3 divides $m$ and $(m,n)\neq (2,2)$ then the answer is still no. The same method works besides that one needs to take modulo $p$ for appropriate choices of $p$, depending on $m$ and $n$. We would be interested in any result beyond this or any alternative solution to the original problem.
The details on this need a good bit of ironing out, but it should generalize a good bit.
By Kirchhoff's Tree Theorem, the number of spanning trees in a graph with vertex set $V$ is equal to $1/|V|$ times the product of the nonzero eigenvalues of its Laplacian matrix.
An array of values will be fixed by any allowable operation if and only if it is an eigenvector of the Laplacian matrix with eigenvalue $0$. In particular, if we can find some prime $p$ that divides the number of spanning trees of the graph determined by adjacency on an $m$ by $n$ grid, there is a nontrivial zero eigenvalue of that Laplacian matrix $\mod p$, and as such there's a vector linearly independent with the all-ones vector that is fixed by any allowable operation. However, because you can divide by $2$, $3$, or $4$ (because there are vertices with degrees $2$, $3$, and $4$), we need to specify that $p$ is not $2$ or $3$.
As such, it won't be possible as long as the number of spanning trees is not $2^a3^b$. In particular, the number of spanning trees on a $2\times 3$ grid is $15$, so $p=5$ should work. (I believe this technically gives a nonconstructive solution to the problem, since one can explicitly enumerate the spanning trees if one wishes, but best not.) One can find the number of spanning trees on an $m\times n$ grid here, which seems to support the claim that as long as $m,n>1$ and $(m,n)\neq (2,2)$, it's not possible.
I haven't been able to prove this (i.e. that it's never $2^a3^b$ except for the aforementioned cases), but on that page, it says that the number of spanning trees of an $m\times n$ grid is
$$\mathrm{Res}\left(U_{n-1}\left(\frac{x}{2}\right),U_{m-1}\left(\frac{4-x}{2}\right)\right),$$
where $\mathrm{Res}$ is the resultant, and $U(n,x)$ is the $n$th Chebyshev polynomial of the second kind. So, we just need to find a prime $p$ modulo which these have a common root. This seems doable...
This direction looks cool! I haven't thought about it in this way and will give it a shot once I have some time I just thought about it for a bit, but I couldn't understand why if $p$ divides the number of spanning trees then there is a nontrivial eigenvector with eigenvalue $0$ modulo $p$. I guess you are trying to say that there exists $\lambda\neq 0$ such that $\lambda\equiv 0\mod p$ and so there is a nontrivial eigenvector. But this assertion is false: consider the $1$ times $3$ grid whose Laplacian has eigenvalues $0,1,3$. Taking $\mod 3$ doesn't give a nontrivial eigenvector with eigenvalue $0$.
Theunknown
18.01.2020 17:21
I have another approach to this question. However this strategy will conclude a different generalization for $(m,n)$ than that of USJL and YaWNeeT. The answer to the original problem is a no. My main strategy is to look for an invariant so that we can actually compute the final value in each unit square, since it's impossible to track the changes of the numbers after every calculations. Now let coordinating the board, label each square as $(i,j)$ where $1\leq i \leq 2018$ and $1\leq j \leq 2019$. We denote $a_{ij}$ as the number in the grid $(i,j)$. Let $\delta_{ij}$ be the number of neighbors of the square $(i,j)$. (for example, $\delta_{11}=2, \delta_{12}=3, \delta_{22}=4$. It is easy to see that $\delta_{ij}\in \{2,3,4 \}$ for any $(i,j)$. Here is the fun part, the key of the problem is to consider this value: $$T = \sum_{(i,j)} \delta_{ij}a_{ij}$$where $(i,j)$ run over all squares of the board. We will show that $T$ is an invariant after each turn. Assuming that after a turn, we have a board with numbers $(b_{ij})$, then we have: $$T'=\sum_{(i,j)} \delta_{ij}b_{ij}= \sum_{(i,j)} \sum_{(k,l) \text{ is the neighbor of } (i,j)} a_{kl}$$for each $(k,l)$ the square $(k,l)$ is the neighbor of exactly $\delta_{kl}$ squares, so $a_{kl}$ will appear exactly $\delta_{kl}$ times in the above sum, hence we have: $$T'=\sum_{(k,l)}\delta_{kl}a_{kl}=T$$which means $T$ remains unchanged after every turns, hence it's an invariant, as claimed. Now assume that after finite step all numbers become equal, let that value be $x$. Set $H = \sum_{(i,j)}\delta_{ij}$. Then we have $$T=x.\sum_{(i,j)}\delta_{ij}=x.H$$so $x=\frac{T}{H}$. A simple calculation shows that $H=16289294$, which clearly have a prime divisor $p \neq 2,3$. Notice that since the original numbers are all integers, and since $\delta_{ij} \in \{2,3,4 \}$ for all $(i,j)$, a simple induction shows that after every turn, the numbers will have the form $\frac{M}{2^a3^b}$ where $M$ is an integer, and so do $x$. So we remain to choose suitable original numbers so that the value $T/H$ doesn't have this form. We choose a board where $a_{11}=1$ and the other numbers are $0$, then $T=2$ and since $H$ has a prime divisor $p \neq 2,3$, $T/H$ clearly can't have the form $\frac{M}{2^a3^b}$ where $M$ is an integer. This contradicts the assumption and prove the problem.
This strategy works for any $m,n$ so that $H$ does not has a form of $2^a3^b$. A simple calculation show that $H=4mn-2m-2n$. So as long as $2mn-m-n$ has a prime divisor other than $2$ and $3$, than this strategy works just fine. Yet this generalization has little correlation with USJL's, so it's not sufficient anyway. Hopefully someone can find a good condition in another approach.
I think this could be a good way to generalize the problem into 3-dimensional cube grids, with slightly different condition for $m,n$.
USJL
21.01.2020 22:11
Theunknown wrote: I have another approach to this question. However this strategy will conclude a different generalization for $(m,n)$ than that of USJL and YaWNeeT. The answer to the original problem is a no. My main strategy is to look for an invariant so that we can actually compute the final value in each unit square, since it's impossible to track the changes of the numbers after every calculations. Now let coordinating the board, label each square as $(i,j)$ where $1\leq i \leq 2018$ and $1\leq j \leq 2019$. We denote $a_{ij}$ as the number in the grid $(i,j)$. Let $\delta_{ij}$ be the number of neighbors of the square $(i,j)$. (for example, $\delta_{11}=2, \delta_{12}=3, \delta_{22}=4$. It is easy to see that $\delta_{ij}\in \{2,3,4 \}$ for any $(i,j)$. Here is the fun part, the key of the problem is to consider this value: $$T = \sum_{(i,j)} \delta_{ij}a_{ij}$$where $(i,j)$ run over all squares of the board. We will show that $T$ is an invariant after each turn. Assuming that after a turn, we have a board with numbers $(b_{ij})$, then we have: $$T'=\sum_{(i,j)} \delta_{ij}b_{ij}= \sum_{(i,j)} \sum_{(k,l) \text{ is the neighbor of } (i,j)} a_{kl}$$for each $(k,l)$ the square $(k,l)$ is the neighbor of exactly $\delta_{kl}$ squares, so $a_{kl}$ will appear exactly $\delta_{kl}$ times in the above sum, hence we have: $$T'=\sum_{(k,l)}\delta_{kl}a_{kl}=T$$which means $T$ remains unchanged after every turns, hence it's an invariant, as claimed. Now assume that after finite step all numbers become equal, let that value be $x$. Set $H = \sum_{(i,j)}\delta_{ij}$. Then we have $$T=x.\sum_{(i,j)}\delta_{ij}=x.H$$so $x=\frac{T}{H}$. A simple calculation shows that $H=16289294$, which clearly have a prime divisor $p \neq 2,3$. Notice that since the original numbers are all integers, and since $\delta_{ij} \in \{2,3,4 \}$ for all $(i,j)$, a simple induction shows that after every turn, the numbers will have the form $\frac{M}{2^a3^b}$ where $M$ is an integer, and so do $x$. So we remain to choose suitable original numbers so that the value $T/H$ doesn't have this form. We choose a board where $a_{11}=1$ and the other numbers are $0$, then $T=2$ and since $H$ has a prime divisor $p \neq 2,3$, $T/H$ clearly can't have the form $\frac{M}{2^a3^b}$ where $M$ is an integer. This contradicts the assumption and prove the problem.
This strategy works for any $m,n$ so that $H$ does not has a form of $2^a3^b$. A simple calculation show that $H=4mn-2m-2n$. So as long as $2mn-m-n$ has a prime divisor other than $2$ and $3$, than this strategy works just fine. Yet this generalization has little correlation with USJL's, so it's not sufficient anyway. Hopefully someone can find a good condition in another approach.
I think this could be a good way to generalize the problem into 3-dimensional cube grids, with slightly different condition for $m,n$.
Maybe I'm reading your solution wrong, but seems like you might have misread the problem. Each time you can choose a subset of squares and make them the average of their neighbors simultaneously. If we don't choose every square some turn, the claimed invariant $T$ might change.
Theunknown
29.01.2020 13:02
Oh yeah that’s probably why I found this problem kinda ez, sry for misreading it but still a nice prob tho.
Nguyen
19.10.2020 05:51
But this involves some higher mathematics. Even though you find out the problem should be divided into 2*3 regions, here is how to find the 2*3 table and modulo (5): The transition matrix is -2 1 1 0 0 0 1 -2 0 1 0 0 1 0 -3 1 1 0 0 1 1 -3 0 1 0 0 1 0 -2 1 0 0 0 1 1 -2 This matrix naturally has one rank-deficiency, but its 1D kernel, generated by [1 1 1 1 1 1] is not what we want. The upper left 5*5 has determinant -15, and the whole matrix indeed has a second rank-deficiency in Z(5). Then its kernel is 2D, with [3 1 3 0 2 0] a possible second generator. MarkBcc168 wrote: This problem is extremely tricky. Here is the official solution.
The answer is $\boxed{\text{NO}}$. Consider the following table.
\begin{tabular}{||c|c|c||c|c|c||c|c|c|c||}
\hline
\hline
3 & 1 & 3 & 3 & 1 & 3 & $\cdots$ & 3 & 1 & 3 \\
\hline
0 & 2 & 0 & 0 & 2 & 0 & $\cdots$ & 0 & 2 & 0\\
\hline
\hline
0 & 2 & 0 & 0 & 2 & 0 & $\cdots$ & 0 & 2 & 0\\
\hline
3 & 1 & 3 & 3 & 1 & 3 & $\cdots$ & 3 & 1 & 3\\
\hline
\hline
3 & 1 & 3 & 3 & 1 & 3 & $\cdots$ & 3 & 1 & 3\\
\hline
0 & 2 & 0 & 0 & 2 & 0 & $\cdots$ & 0 & 2 & 0\\
\hline
\hline
0 & 2 & 0 & 0 & 2 & 0 & $\cdots$ & 0 & 2 & 0\\
\hline
3 & 1 & 3 & 3 & 1 & 3 & $\cdots$ & 3 & 1 & 3\\
\hline
\hline
$\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\ddots$ & $\vdots$ & $\vdots$ & $\vdots$ \\
\hline
3 & 1 & 3 & 3 & 1 & 3 & $\cdots$ & 3 & 1 & 3\\
\hline
0 & 2 & 0 & 0 & 2 & 0 & $\cdots$ & 0 & 2 & 0\\
\hline
\hline
\end{tabular}
We will consider this table in modulo $5$ soon but we have to overcome some technicalities first. At any point, the denominator of each entry is in form $2^a\cdot 3^b$, which is not divisible by $5$. Hence we can take $\frac{a}{b}\equiv ab^{-1}\pmod 5$ where $b^{-1}$ be the inverse of $b$ in modulo $5$.
It's straightforward to verify that if we move at any cells, the cell preserve its value in modulo $5$. So, we can't make all cells have same value in modulo $5$ and we are done.
YaoAOPS
17.09.2023 06:57
Unironically worse then apmo 2019/5.
We show this is impossible for all $2n \times 3m$ by constructing a nontrivial board in ${\mathbb F}_5$.
For a $2 \times 3$ grid, we have the table \[ \begin{tabular}{|c|c|c|} \hline 2 & 1 & 2 \\ \hline 3 & 4 & 3 \\ \hline \end{tabular} \]which works.
For the more general case, we can reflect this table across its borders as needed.
carefully
18.07.2024 06:28
Seriously, is there really no combinatorial solution using monovariant (that would work for real numbers and for any size of board)??? It's super counter-intuitive that there's no such solution.
Martin2001
01.09.2024 17:21
Tile it with $2x3$ grids that are $2,3,2 \pmod 5$ in the top row and $1,0,1 \pmod 5$ in the bottom row of three in that order. Note that when we take the average, the indices stay the same. Therefore we're done$.\blacksquare$