Let $k$ and $s$ be positive integers such that $s<(2k + 1)^2$. Initially, one cell out of an $n \times n$ grid is coloured green. On each turn, we pick some green cell $c$ and colour green some $s$ out of the $(2k + 1)^2$ cells in the $(2k + 1) \times (2k + 1)$ square centred at $c$. No cell may be coloured green twice. We say that $s$ is $k-sparse$ if there exists some positive number $C$ such that, for every positive integer $n$, the total number of green cells after any number of turns is always going to be at most $Cn$. Find, in terms of $k$, the least $k$-sparse integer $s$. Proposed by Nikolai Beluhov.
Problem
Source: 2018 RMM Shortlist C4
Tags: combinatorics
yayups
27.03.2020 06:39
Solution with william122.
(it's for $k=2$ but generalizes readily) shows that we can create a chain of squares that can zig-zag in any direction. The bottom left part of the image then shows how we can make $Cn^2$ of the squares green. The difficult part is to show that $s=3k^2+2k$ is $k$-sparse. Call a green square good if it is used to generate $s$ more green squares. Draw an arrow from a good square $a$ to another good square $b$ if $b$ is generated from $a$. In this case, write $a=f(b)$ (reverse arrow diagram). Since there are at most $s-1$ non-good green squares for each good square, it suffices to show that the good squares can't achieve positive density. Call a good square non-ideal of type I if $f(a)\to a$ is not a translation by $(\pm k,\pm k)$. Call a good square non-ideal of type II if $f^2(a)\to a\to a$ are both translations by $(\pm k,\pm k)$, but they are orthogonal. We have the following key claim. Claim: There are at most $100k$ non-ideal good squares. Proof: Suppose there are $N$ total good squares. Our goal is to bound the total area of all the $(2k+1)\times(2k+1)$ squares centered at the good squares. Start from the original green square (which is also good), and add all the good squares by following the arrows (so we can't add $a$ unless $f(a)$ has already been added). If we add a non-ideal good square of type I, then we are adding at most $(2k+1)^2-(k+1)(k+2)<(3k^2+2k)-k$ area. If we add a non-ideal good square of type II, then we are adding at most $(2k+1)^2-(k+1)^2-k=(3k^2+2k)-k$ area. Thus, the total area is at most \[(2k+1)^2+(N-1-\ell)[(2k+1)^2-(k+1)^2]+\ell[(2k+1)^2-(k+1)^2-k],\]which is \[N[3k^2+2k]+(k+1)^2-\ell k.\]Now all $1+(N-1)s$ generated squares have to fit in this area, so we have \[1+(N-1)[3k^2+2k]\le N[3k^2+2k]+(k+1)^2-\ell k,\]so $\ell\le 4k+4\le 100k$. $\blacksquare$ Note that if we have an arrow from $a\to b$ and $a\to c$, then one of $b$ or $c$ is non-ideal. Thus, there are at most $100k$ good squares that point to more than one good square, so the entire arrow diagram can be partitioned into at most $(3k^2+2k)^{100k}$ chains. We see that for each pair of consecutive arrows in a chain that switch direction, there is a non-ideal square. Thus, the chain switches direction at most $100k$ times, so the chain can't cover positive density. Since there are at most $(3k^2+2k)^{100k}$ chains, the good squares do not cover positive density, as desired.
A02
29.05.2020 11:15
yayups wrote: Solution with william122.
(it's for $k=2$ but generalizes readily) shows that we can create a chain of squares that can zig-zag in any direction. The bottom left part of the image then shows how we can make $Cn^2$ of the squares green. The difficult part is to show that $s=3k^2+2k$ is $k$-sparse. Call a green square good if it is used to generate $s$ more green squares. Draw an arrow from a good square $a$ to another good square $b$ if $b$ is generated from $a$. In this case, write $a=f(b)$ (reverse arrow diagram). Since there are at most $s-1$ non-good green squares for each good square, it suffices to show that the good squares can't achieve positive density. Call a good square non-ideal of type I if $f(a)\to a$ is not a translation by $(\pm k,\pm k)$. Call a good square non-ideal of type II if $f^2(a)\to a\to a$ are both translations by $(\pm k,\pm k)$, but they are orthogonal. We have the following key claim. Claim: There are at most $100k$ non-ideal good squares. Proof: Suppose there are $N$ total good squares. Our goal is to bound the total area of all the $(2k+1)\times(2k+1)$ squares centered at the good squares. Start from the original green square (which is also good), and add all the good squares by following the arrows (so we can't add $a$ unless $f(a)$ has already been added). If we add a non-ideal good square of type I, then we are adding at most $(2k+1)^2-(k+1)(k+2)<(3k^2+2k)-k$ area. If we add a non-ideal good square of type II, then we are adding at most $(2k+1)^2-(k+1)^2-k=(3k^2+2k)-k$ area. Thus, the total area is at most \[(2k+1)^2+(N-1-\ell)[(2k+1)^2-(k+1)^2]+\ell[(2k+1)^2-(k+1)^2-k],\]which is \[N[3k^2+2k]+(k+1)^2-\ell k.\]Now all $1+(N-1)s$ generated squares have to fit in this area, so we have \[1+(N-1)[3k^2+2k]\le N[3k^2+2k]+(k+1)^2-\ell k,\]so $\ell\le 4k+4\le 100k$. $\blacksquare$ Note that if we have an arrow from $a\to b$ and $a\to c$, then one of $b$ or $c$ is non-ideal. Thus, there are at most $100k$ good squares that point to more than one good square, so the entire arrow diagram can be partitioned into at most $(3k^2+2k)^{100k}$ chains. We see that for each pair of consecutive arrows in a chain that switch direction, there is a non-ideal square. Thus, the chain switches direction at most $100k$ times, so the chain can't cover positive density. Since there are at most $(3k^2+2k)^{100k}$ chains, the good squares do not cover positive density, as desired. Nice solution, mine is the same. At the end I don't think you mean positive density since that's a weaker result then what's required. E.g. if the number of green squares covered O(nlogn) squares that's not positive density but also not O(n).
yayups
29.05.2020 13:14
@above fair point but I think my solution shows $O(n)$ right?
A02
02.07.2020 18:18
yayups wrote: @above fair point but I think my solution shows $O(n)$ right? Yeah the solution is fine.
Idio-logy
11.12.2020 00:53
Answer: the least $k$-sparse integer is $3k^2+2k = (2k+1)^2 - (k+1)^2$. Construction is the same as post #2 and omitted.
We prove that when $r = 3k^2+2k$, then the total number of green cells after any number of turns is $O(n)$. Let $m$ be the number of turns. Suppose that at each turn, when we pick a green cell, we also draw a $(2k+1)\times (2k+1)$ square with the picked green cell at its center (so that all green cells we color in that turn lie inside the square we drew in that turn). For the rest of the solution, we are referring to these squares when we say the word ``square''. We say a square is bad if it overlaps strictly more than $(k+1)^2$ cells with previous squares.
Lemma. The total number of cells covered by these $m$ squares is at most $m(3k^2+2k) + (k+1)^2 - B$, where $B$ is the number of bad squares.
Proof. The square we drew in the first turn covers $(2k+1)^2$. The square we drew in the $t$th turn, for $t\ge 2$, must be centered at some green cell, which by definition lies inside some square that we already drew. Thus, the square drawn in the $t$th turn must have at least $(k+1)^2$ overlap with previous squares, so it covers at most $(2k+1)^2-(k+1)^2 = 3k^2+2k$ new cells. The bad squares, however, cover at most $3k^2+2k-1$ new cells. $\square$
On the other hand, in each turn we colored $3k^2+2k$ new green cells, so there are $m(3k^2+2k)$ green cells in total. This gives us that there are at most $(k+1)^2$ bad squares.
Consider a graph with the squares as vertices, and we draw an edge between two vertices if the center of one square lies inside the other square (note that this relation is symmetric). Then the resulting graph is connected, so there are at least $m-1$ edges. Furthermore, we color an edge blue if the two squares are offset by exactly $(\pm k, \pm k)$, and color the edge red otherwise. Notice that for a red edge, at least one of its endpoints is bad. Because each vertex has degree at most $(2k+1)^2$, there are at most $(k+1)^2(2k+1)^2$ red edges, which is a constant that does not depend on $m$ and $n$.
Now, we focus on the blue edges. In fact, we can embed the blue edges and their vertices into the $n\times n$ square, with each vertex corresponding to the center of the square it represents. Then since the vertices are all offset by some combination of $(\pm k, \pm k)$, each connected component forms a subset of some square lattice tilted by 45 degrees.
Claim. We can color at most $8(k+1)^2$ blue edges yellow, such that any two blue edges incident to the same vertex form an 180-degree angle.
Proof. Suppose two blue edges incident to the same vertex form an 90-degree angle, then among the three vertices (squares) involved, at least one of them is bad. Then there are at most $8(k+1)^2$ cases where this can happen, so we can color at most $8(k+1)^2$ blue edges into yellow in order to eliminate all of them. $\square$
The remaining graph formed by blue edges is a collection of straight chains. Each chain only has a length of $O(n)$ by definition. Furthermore, because the graph is connected, for each chain there exists a vertex that is adjacent to either a yellow edge or a red edge. Thus, there are at most $O(n)$ blue edges.
Summing these together, we have
\[m-1 \le \#(\text{edges}) \le \#(\text{blue}) + \#(\text{red}) + \#(\text{yellow}) = O(n) + O(1) + O(1) = O(n),\]which implies that there are $O(n)$ green cells.