$n^2$-Grid $3n$-Coloring Game: Can we color a n-square grid with 3n colors s. t. we can't select n colors to get an histogram with $\Theta(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 $\Theta(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 $\Theta(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)$. 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

In order for Bob to win, he needs that at least $\delta n$ columns have values at least $\delta n$ each. So Alice just needs to shuffle the colors to prevent this.

In other words, we need $n$ subsets of $[3n]$, each of cardinality $\delta n$, such that the union of every $\delta n$ of them has cardinality larger than $n$.

Pick those sets at random. For every of $n\choose \delta n$ collections of $\delta n$ of them, and for every of $3n\choose n$ subsets $B$ of $[3n]$, the probability that the union of the collection fits into $B$ is at most $3^{-\delta^2n^2}$. Hence the probability that Bob wins is at most $$ {n\choose \delta n}{3n\choose n}3^{-\delta^2n^2} $$ which is much smaller than $1$.

In fact, if Bob wants a score of $\alpha n$, the same works when $$ {n\choose \alpha}{3n\choose n}3^{-\alpha^2}<1, $$ which eventually holds for $a>c\sqrt n$ with an appropriate constant $c$.