1
$\begingroup$

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.

$\endgroup$

1 Answer 1

0
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ But it seems to me that the real score Bob always can achieve is around $n\mathop{\mathrm{polylog}}n$... $\endgroup$ Apr 28, 2022 at 10:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.