# 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?

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.

• As a (minor) side note, the rule "Bob wins if $V_c(B)$ is $\Omega(n^2)$" technically does not leave us with any way to judge if a particular game is a victory. Suppose we are playing on a $100 \times 100$ grid and Bob does really badly and scores $6$ points. Is that $0.0006 n^2$, which is $\Omega(n^2)$? That can't be meaningfully answered. Better to forget "winning" entirely and just ask "Does Bob have a strategy that asymptotically scores $\Omega(n^2)$ points?" May 5, 2022 at 18:27

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.