Ivan has a $n \times n$ board. He colors some of the squares black such that every black square has exactly two neighbouring square that are also black. Let $d_n$ be the maximum number of black squares possible, prove that there exist some real constants $a$, $b$, $c\ge 0$ such that; $$an^2-bn\le d_n\le an^2+cn.$$ Proposed by Ivan Chan Kai Chin
Problem
Source: Own. Malaysian APMO CST 2024 P4
Tags: combinatorics
carefully
24.02.2024 19:23
Seems similar to my proposed problem, but with a cycle instead of a path. I think the value $a=\frac{2}{3}$ still holds though.
Anzoteh
26.02.2024 18:51
I was the supplier of the official solution; here's the sketch (my only contribution to this CST, and also this solution matches very closely to what the proposer Ivan has in mind beforehand but he happened to be too busy to write it down).
$a = 2/3$; $b=8$ and $c=4$ works for me.
the black squares not on the boundaries must have two white neighbours, and considering that each white square has $\le 4$ neighbours, the black:white ratio cannot exceed 4:2 = 2:1 (+ some boundary ones).
the main motivation is to isolate all except $O(n)$ of the white squares. To this end, we define a $k$-dragon as a loop with black squares forming a cycle and white squares inside the cycle and all isolated, and occupying a diagonal of length $k$; a 6-dragon is attached as an example. One can show that a $k$-dragon has $4(k-1)$ black squares, and we can tile a 6-, 12-, $\cdots$, $6k$, $6(k-1)$, $\cdots$, 12-, 6-dragon on the diagonals (here $k=\lfloor \frac{n}{6}\rfloor$). This estimate gives $\frac{2}{3}n^2 - 8n$.
Attachments:
