1. **Problem statement:** We have an infinite chessboard with an $n$-coloring: one green square, one blue square, and $n$ red squares. A coloring is *valid* if a rook can move from green to blue without passing through red squares. An $n$-coloring is *$m$-valid* if the rook can do this in $m$ moves or fewer. A function $f:\mathbb{N}_0 \to \mathbb{N}_0$ is *démentielle* if for all $n$, every valid $n$-coloring is $f(n)$-valid. We want to show: - For $c \in \mathbb{R}_0^+$, $g_c(n) = \lfloor c n + 100 \rfloor$ is démentielle if and only if $c \geq 2$. - Determine if $h(n) = \lfloor 2n - 2\sqrt{3n} + 100 \rfloor$ is démentielle. --- 2. **Key observations and formula:** - The rook moves horizontally or vertically. - Minimum moves from green to blue without obstacles is at least the sum of horizontal and vertical distances. - Red squares block paths, increasing moves needed. - The minimal number of moves needed to bypass $n$ red squares grows with $n$. --- 3. **Step 1: Show $g_c$ is démentielle iff $c \geq 2$** - **If $c < 2$:** Construct a valid $n$-coloring where the rook must make more than $\lfloor c n + 100 \rfloor$ moves. Since the rook must detour around $n$ red squares, the minimal moves grow roughly like $2n$ (one horizontal and one vertical detour per red square). For $c < 2$, $c n + 100 < 2n$ for large $n$, so $g_c(n)$ underestimates the moves needed. Hence, $g_c$ is not démentielle. - **If $c \geq 2$:** The rook can always find a path in at most $2n + 100$ moves. Because each red square can force at most one horizontal and one vertical detour, total moves needed $\leq 2n +$ constant. Thus, $g_c(n) = \lfloor c n + 100 \rfloor \geq 2n + 100$ bounds the moves needed. So every valid $n$-coloring is $g_c(n)$-valid. Hence, $g_c$ is démentielle. --- 4. **Step 2: Determine if $h(n) = \lfloor 2n - 2\sqrt{3n} + 100 \rfloor$ is démentielle** - Since $h(n)$ is close to $2n$ but subtracts $2\sqrt{3n}$, it is slightly less than $2n$ for large $n$. - The minimal moves needed are about $2n$ (as above). - The negative term $-2\sqrt{3n}$ grows slower than $n$, but for large $n$, $h(n) < 2n$. - Therefore, for large $n$, $h(n)$ underestimates the moves needed. - So there exist valid $n$-colorings that are not $h(n)$-valid. - Hence, $h$ is *not* démentielle. --- **Final answers:** - $g_c$ is démentielle if and only if $c \geq 2$. - $h$ is not démentielle.