, 2023

The largest $K = 5 \times 222^2$; in general, for a $3N \times 3N$ grid, $K = 5N^2$.

First we prove $K \le 5N^2$. Color the grid as in the figure above, and note that in each turn the necromancer can only increase skeletons on at most four white blocks, so the paladin can always keep the skeleton count on the white region at $0$, so the number of doomed blocks the necromancer can possibly guarantee to create is at most the number of gray blocks, namely $5N^2$.

Next we prove $K \ge 5N^2$. In fact, we may consider the following strengthened version of the game: when it is the paladin's turn, he instead chooses five blocks within the $3 \times 3$ region that the necromancer has just increased skeletons in, and decreases the skeleton count by one in every block on the entire grid except these five blocks. Clearly, if in the strengthened version the necromancer can guarantee $K \ge 5N^2$, then he can also do so in the original version. Note that, for a $3 \times 3$ region, there are a total of $M = \binom{9}{5}$ ways for the paladin to choose five of its blocks. Also note that, combining both players' moves, this is equivalent to increasing the skeleton count by $1$ in the five blocks chosen by the paladin, keeping the skeleton count unchanged in the remaining four blocks of the $3 \times 3$ region, and decreasing the skeleton count by $1$ in every other block on the grid.

Consider the necromancer repeatedly targeting the same $3 \times 3$ region for $M\ell$ consecutive turns. By the pigeonhole principle, among all $M$ ways of choosing five blocks out of the $3 \times 3$ region, there must be one that the paladin selects at least $\ell$ times. From the discussion in the previous paragraph, this means that within this $3 \times 3$ region, there are at least five blocks whose skeleton count is $\ge \ell$.

Now, partition the grid into $N^2$ disjoint $3 \times 3$ regions, and number them $0, 1, \dots, N^2 - 1$. Then, starting from the region with the largest number, we perform the following actions in sequence: for the region numbered $b$, let the necromancer repeatedly target that region for $C = 10^6 M (M+1)^b$ consecutive turns. By the discussion above, these $C$ turns guarantee that five blocks in this region have their skeleton count increased to at least $10^6 (M+1)^b$, and afterward each subsequent turn will decrease this count by $1$. However, after completing the $C$ turns for region numbered $b$, we will only perform actions on the regions numbered $b-1$ down to $0$, and the total number of turns for these actions is $10^6 M \{(M+1)^{b-1} + (M+1)^{b-2} + \dots + 1\} = 10^6 \{(M+1)^b - 1\}$, so the region numbered $b$ will have at least five blocks whose skeleton count is no less than $10^6 (M+1)^b - 10^6 \{(M+1)^b - 1\} = 10^6$. The above reasoning holds for all $b$, so there are $5N^2$ doomed blocks. This completes the proof.