n^2-Grid 3n-Coloring Game: Can we color a n-square grid with 3n colors s. t. we cannot choose n colors to obtain an histogram with $\Omega(n^2)$ area?

Question

The coloring game is a game played between Alice and Bob. There exists a grid of size $n \times n$, where $n$ is a strictly positive integer. Each cell of the grid can be colored with a color that belongs to the set $\mathit{Colors} = [1:3n] = \{ 1,2,...,3n \} $. Importantly, black is a special color that does not belong to $\mathit{Colors}$.

Alice starts the game by coloring the entire grid using the aforementioned colors in the $\mathit{Colors}$ set (see figures 1 and 2). Formally, Alice chooses a coloring function $c$ that maps every pair $(x,y) \in [1:n] \times [1:n]$ to $c(x,y) \in \mathit{Colors}$. The set of coloring functions is noted $Coloring$. Once Alice has finished the coloring of the entire grid, it is Bob's turn.

An example of coloring with $n=4$, i. e. with $3n=12$ colors in a grid of dimension $4*4$

The previous example with integers instead of colors.

Bob selects a set $B \subset \mathit{Colors}$ of at most $n$ colors (i.e., $|B| \leq n$).

The value of column $j$ (for $c \in Coloring$ and $B \subset \mathit{Colors}$) is $V_c(B, j)$ is the $y$-index of the first cell in column $j$ that is not assigned a color in $B$. Formally, $V_c(B, j) = max( \{ h \in [1:n+1] | \forall z \in [1:h-1], c(j,z) \in B \} )$. The value of the grid $V_c(B) = \sum\limits_{j = 1}^{n} V_c(B, j)$ is the sum of the values of the columns. The score of a coloring $c$ (noted $score(c)$) is the maximum value $V_c(B)$ of the grid for any set $B \subseteq Colors$ where $|B| \leq n$. Formally, $score(c) = \underset{\begin{subarray}{c} B \subset Colors, \\ |B|\leq n \end{subarray}}{max} V_c(B)$

Bob has chosen the colors $B = \{ 1,2,4,12 \}$. The cells in $B$ that compose a continuous column are surrounded with black frame. The cells in $B$ that are not part of a continuous column are surrounded with white frame. The value $V_c(B)$ is then $2+3+1+4 = 10$.

Bob wins the game if the value of the grid $V_c(B)$ is $\Omega(n^2)$; otherwise, Alice wins. Is there a strategy that ensures Alice's win?

Formally, what is the asymptotic value of $\underset{c \in Coloring}{min} score(c) = \underset{c \in Coloring}{min} (\underset{\begin{subarray}{c} B \subset Colors, \\ |B|\leq n \end{subarray}}{max} V_c(B))$ ? Is it $\Omega(n^2)$ or $o(n^2)$ ?

We stress that Alice and Bob start the game when $n$ is fixed and known by each player. (If $n$ is increased, colors are erased and the game start with a clean grid with the new value of $n$.)

Tip 1: Naive coloring

A coloring function $c$ is said naive if it preserves the order of colors in each column, i. e. if $\forall x,x',y_1, y_1', ,y_2,y_2' \in [1:n]$ s. t. $y'_2 - y_1' = y_2-y_1$, we have $c(x, y_1) = c(x', y'_1)$ implies $c(x, y_2) = c(x', y'_2) $. This is the case for the example (the sequences $(1,11,9), (2, 12,10)$ are preserved every time one of their component is met).

A naive coloring function cannot be a winning strategy. Indeed, by pigeonhole principle, it exists a color $q$ represented $\Omega(n)$ times in the first half of the grid. We note $Q = \{ (x,y) \in [1:n]^2 | y \leq n/2, c(x,y) = q \} $ with $|Q| = \Theta(n)$. We note, $(x_{min}, y_{min})$ (resp. $(x_{max}, y_{max})$) the couple of coordinates of $Q$ where $y_{min}$ (resp. $y_{max}$) is the minimum (resp. maximum) height $y$ for a pair $(x,y) \in Q$. Bob can simply choose $B = B_{up} \cup B_{down} \cup \{ q \}$ where $B_{up}$ represents the colors above $q$ at a height below $n/2$ ($B_{up} = \{ (x_{min},y) | y \in [y_{min}: \lfloor n/2 \rfloor] \} $) and $B_{down}$ represents the colors below $q$ ($B_{down} = \{ (x_{max},y) | y \in [1: y_{max}] \} $). We still have $|B| \leq n$ and the score will be the result of $\Theta(n)$ columns of height $\Theta(n/2)$ that is $\Theta(n^2)$ (and so $\Omega(n^2)$ too). In the example we could have $q = 1$, $(x_{min}, y_{min}) = (1,1)$, $(x_{max}, y_{max}) = (3,2)$, $B_{down} = \{ 3 \}$, $B_{up} = \{ 11 \}$.

Intuitively, to beat Alice in case of non naive coloring, Bob should find $n$ colors that are often in the same filled columns.

Answer 1

Alice can win; in fact, just by coloring at random, Alice is very likely to absolutely crush Bob.

The number of ways to choose a histogram with area $S$ is at most the number of ways to write $S = S_1 + S_2 + \dots + S_n$ where $S_1, S_2, \dots, S_n$ are nonnegative integers, which is $\binom{S+n-1}{n-1}$. The number of ways to choose $n$ colors is $\binom{3n}{n}$. Finally, the probability that a given histogram with area $S$ only contains $n$ fixed colors, when we color at random, is $(\frac{n}{3n})^S = (\frac13)^S$.

Therefore in a random coloring, the expected number of histograms of area $S$ that have only $n$ or fewer colors is at most $\binom{S+n-1}{n-1} \binom{3n}{n} (\frac13)^S$.

Very crudely, we can bound $\binom{S+n-1}{n-1}$ by $2^{S+n}$ and $\binom{3n}{n}$ by $2^{3n}$, getting $2^{S+4n}3^{-S}$. So if we set $S = 7n$, the expectation is at most $2^{11n}3^{-7n} = (\frac{2048}{2187})^n$, which is always less than $1$ and tends to $0$ in the limit.

To score at least $n+S$ points, Bob must find a histogram of area at least $S$ that has only $n$ colors in it. Therefore with a positive (and usually very high) probability, a random coloring will not leave Bob with a way to score $8n$ points.