For all integers $x,y$, a non-negative integer $f(x,y)$ is written on the point $(x,y)$ on the coordinate plane. Initially, $f(0,0) = 4$ and the value written on all remaining points is $0$. For integers $n, m$ that satisfies $f(n,m) \ge 2$, define 'Seehang' as the act of reducing $f(n,m)$ by $1$, selecting 3 of $f(n,m+1), f(n,m-1), f(n+1,m), f(n-1,m)$ and increasing them by 1. Prove that after a finite number of 'Seehang's, it cannot be $f(n,m)\le 1$ for all integers $n,m$.
Problem
Source: 2021 Korea Winter Program Test1 Day2 #7
Tags: combinatorics, coordinate
niksic
25.03.2021 17:30
Say $f$ counts the number of tokens on every point. Denote by $M$ the total number of tokens and by $N$ the total number of points with at least one token on it. First, notice that if a point has a non-zero number of tokens on it, it will never again have zero tokens on it $(*)$. Also notice that $M$ increases by exactly two after every move, so $M=4+2k$ after $k$ moves. Divide the moves into type $1, 2, 3$ or $0$, depending on how much $N$ increases after it. Say a point other than $(0, 0)$ makes a 3-move. Note that, due to $(*)$, a point can make at most one 3-move. We now pair it with a 0 or 1-move. Because the point we're talking about isn't the origin, it must have received it's $\geq 2$ token from a 'fuel point'. If it has more then one fuel point, then it can't make a 3-move. So the fuel point has given it a token at least twice, meaning one of it's moves is a 0 or 1-move. Pair these two. We now claim there's at most one overlap in this pairing. Say two points link to a same fuel point. If the fuel point isn't the origin, it had to be fueled from another point - but by drawing the picture we see that one of the two points couldn't have made a 3-move afterwards. Putting everything together, by this pairing which fails at most twice (once for the origin and once for a neighbor of the origin), we see that $N\leq 1+2k+2 = 3+2k$ after $k$ moves. Bringing everything together $\frac{M}{N} > 1$ always, so there has to be some point with at least two tokens on it $\blacksquare$ Apologies for the poor explanation
shanaga
18.09.2021 11:08
We put 4 tokens each with weight 1 at $(0,0)$. Each move one token is splitted into 3 tokens each with $\frac{1}{3}$ of original weight. Then the total weight of tokens is constant 4. If $f(n,m)\le 1$ for all $(n,m)$, then each point owns at most one token. Notice that the token at $(x,y)$ weighes at most $3^{-|x|-|y|}$, so the total weight is at most $\sum\limits_{(x,y)\in\mathbb{Z}^2}3^{-|x|-|y|}=1+\sum\limits_{d=1}^\infty 4d\cdot3^{-d}=4$. However after finite moves the equality can't hold, contradicition.