We'll cover the board with checkers and ghost-checkers. For each checker we'll have two ghost-checkers available. So we'll have $3k$ units available, where $k$ is the number of checkers. For each checker X with just two neighbors A, B: place the two ghost-checkers for X on the two squares adjacent to X different from A and B. For each checker with three neighbors, place one of its ghosts on the fourth adjacent square and keep the other. For each checker with four neighbors, keep both of its ghosts. For each checker X with just one neighbor A, place the two ghost-checkers for X on the squares adjacent to X different from A and its opposite. (Of course there are no lonely checkers since the graph is connected). When we're done there may be squares covered more than once, and there may be ghosts outside the board; it doesn't matter. The only squares that may be left uncovered are those squares A with just one checkered neighbor X, where X has just one checkered neighbor itself (call it Y), and A, X, Y are collinear. Now note that, for the connected graph formed by the checkers, the number of "endpoints" of the graph (that is, checkers with just one neighbor) is at most 2+the number of checkers with 3 neighbors+twice the number of checkers with 4 neighbors (the event "a checker with 4 neighbors" is equivalent to the event "a checker with 3 neighbors" ocurring two different times), which is easy to prove by induction (take an endpoint, go along the graph till you find a point where the path has two or more branches, and remove the string connecting the taken endpoint to the rest of the graph; if we find no points where it branches out, it must be a simple path with just 2 endpoints). This means that using the checkers we'd kept before, we can cover all the yet uncovered squares except at most 2, so $3k \geq n^2-2$, which is what we wanted to prove.

Let us place the checkers on the board as follows: place one checker on the board to start, and then continually place a checker adjacent to one that has already been placed. Since any arrangement of checkers that satisfies the problem must be connected (i.e. (b)), we can form any arrangement of checkers in this manner. Call a square "on" if it has a checker on it or it is next to a square that has a checker. By (a), we require an arrangement for which every single square is on. When we place the first checker, at most five squares are turned on. For every subsequent checker we place, at most three squares are turned on (the place we just filled and the filled space next to it being already on). If we fill the board with $ k$ checkers, we have turned on at most $ 5 + 3(k-1) = 3k+2$ checkers. Since there are $ n^2$ squares on the board, we need $ 3k+2 \ge n^2$ or $ k \ge \frac{n^2-2}{3}$.

How about the result if this just has only the first restriction? Is it 12 in the case 5*5 blackboard?

What about when n=2? Then the problem requires that we need at least 2/3, or 1 checker. But no matter where we put it the square diagonally from that square doesn't share a side with that square with the checker.

That's true and doesn't contradict the statement of the problem. (It does show that the statement is not sharp for $n = 2$, since in that case at least 2 checkers are needed.) @ghjk, two years later: no, 12 is much too large for the $5 \times 5$. For example, my first attempt did it in 8. In general, the best case should be approximately $\frac{n^2}{5}$ (but slightly larger due to edge effects).

Suppose there are $f(n)$ checkers on the board (and $n^2-f(n)$ empty squares), so from (b), the checkers form a connected graph $G$. Now let $X$ denote the number of pairs of neighboring squares both containing checkers and $Y$ denote the number of pairs of neighboring squares with exactly one containing a checker. Then $X$ is simply the number of edges in $G$, so $X\ge f(n)-1$. Furthermore, since each checker borders at most four other squares, we have $2X+Y\le4f(n)$, so $Y\le4f(n)-2X$. But (a) tells us that \[n^2-f(n) \le Y\le4f(n)-2X,\]so \[5f(n)\ge n^2+2X\ge n^2+2f(n)-2\implies f(n)\ge\frac{n^2-2}{3},\]as desired.

Solution with vsathiam.

Solution from Twitch Solves ISL: Take a spanning tree on the set $V$ of checkers where the $|V|-1$ edges of the tree are given by orthogonal adjacency. By condition (a) we have \[ \sum_{v \in V} (4-\deg v) \ge n^2 - |V| \]and since $\sum_{v \in V} \deg v = 2(|V|-1)$ we get \[ 4|V| - \left( 2|V|-2 \right) \ge n^2 - |V| \]which implies $|V| \ge \frac{n^2-2}{3}$.

statement (b) says that the squares with checkers on them form a polyomino finally, statement (a) says that if we "extend" the polyomino outward (this probably doesn't make sense oops) the area must be $n^2$ its easy to see that extend the polyomino, maximum area is $3k+2$ given $k$ checkers (because we form a $1$ by $k$ rectangle) therefore number of checkers satisfies $3k+2\geq n^2$ and we are done

to show max is $3k+2$ area, note that the first tile adds $5$ squares, and each successive one must add only $3$ at most

Let $m$ be the number of checkers. We say that a cell is good if it either contains a checker or is adjacent to a cell that contains a checker. Since the order we place them in does not matter, we placed them in an order such that each checker after the first is placed next to an existing checker (this is possible due to the connected component condition). Note that the first checker can make at most 5 cells good. Each additional checker can make at most 3 cells good (since the cell its placed on is already good and it is "blocked" in one of the directions by an existing checker). Therefore, we must have $5+3(m-1)\geq n^2$, so $$m\geq \frac{n^2-2}{3}$$ Remark: this was somewhat motivated by the very peculiar condition $\frac{n^2-2}{3}$. in particular, this is never an integer due to 2mod3, so this motivates a method where each checker placed counts as multiple "things" (in this case good cells)

Let $k$ be the number of squares with checkers. First, notice that the number of pairs of adjacent squares with one filled and one empty is at least $n^2-k$ (the number of empty squares). On the other hand, the number of pairs of adjacent squares, both filled, is at least $k-1$. However, in total, there are at most $4k$ pairs of adjacent squares, at least one of which is filled. Therefore, we have the inequality $$n^2-k+2(k-1) \leq 4k \iff k \geq \frac{n^2-2}3,$$as required.

We count the pairs of adjacent squares such that one is filled and one is empty. If there are $k$ filled squares, the maximum perimeter of the filled squares is $2k+2$ as each new block after the original one adds at most $2$ to the perimeter of the filled squares. The minimum perimeter is $n^2-k$ as each non-filled square must share a side with a filled square. Hence, $2k+2\ge n^2-k$, as desired. $\square$

Consider a square to be "covered" if it is covered by a checker or shares a side with a square covered by a checker. First place down one checker. This checker can "cover" at most $5$ squares. For each checker placed down after that, by problem conditions, it must share a side with another checker, meaning that it can "cover" at most $3$ new squares. This means that we need at least \[1+\frac{n^2-5}{3},\]or $\frac{n^2-2}{3}$ checkers.

We count the total number of cells in two ways: First, it is obviously $n^2$. On the other hand, it is the number of cells with checkers along with the number of cells that are adjacent to checkers. Let the number of cells with checkers be $k$. Then from the second condition, all checkers must be able to form a path, and so each checker must be adjacent to two others except for the "end" checkers if they exist, giving a maximum of $2k+2$ in this case. Thus, we have \[ 3k+2 \leq n^2 \implies k \geq \frac{n^2-2}{3} \]completing the proof. $\blacksquare$

Let there be $k$ squares with checkers in them. It is clear that they border at most $2(k-2)+3 \cdot 2=2k+2$ squares because of the first condition. Thus, \[3k+2 \ge n^2 \iff k \ge \frac{n^2-2}{3}. \ \square\]

This is a funny way to solve. Connect squares with checkers in them to become a spanning tree $V$ Consider the sum $\sum_{v \in V} (4-\text{deg}(v))$ Note that in this sum each square without a checker on it gets counted so $$\sum_{v \in V} (4-\text{deg}(v)) \geq n^2- |V|$$$$4|V|-2(|V|-1) \geq n^2-|V|$$$$|V| \geq \tfrac{n^2-2}{3}. \square$$

Let $w$ be the number of white cells and let $b$ be the number of black cells. Then each white cell has at least one black neighbor. Consider the graph on the black cells where there is an edge between two black cells if they share an edge. Since this graph is connected, it must have at least $b-1$ edges. Therefore, the black cells can satisfy at most $2b+2$ white cells, so $w\le 2b+2$. Therefore, $n^2=w+b\le 3b+2$, which implies the wanted result.

Let $A$ and $B$ be the set of squares with and without a checker, respectively. A upper bound for $|B|$ is \[\sum_{a \in A} (4-\deg a) = 4|A| - \sum_{a \in A} (\deg a)\]. The graph of $A$ is connected, so it contains at least $|A|-1$ edges, and thus \[4|A| - \sum_{a \in A} (\deg a) \ge 4|A| - 2(|A|-1) \ge |B| = n^2 - |A| \implies |A| \ge \frac{n^2-2}{3}. \quad \blacksquare\]

Let $C_i$ be the number of checkers next to square $i$, and let $a$ be the total number of checkers. The checkers must be connected, so the first time we add a checker nothing happens with the checker, but after adding a checker next to it, the count of $\sum C_i$ goes up by $2$, and goes up by $2$ for each additional checker we put next to another checker. Note that in this count, we have not yet included $C_i$ for squares without checkers. When we do, the count goes up by at least $n^2-a$, because every non checker square has at least one checker next to it. So in total, we have that \[\sum_{i=1}^{n^2}C_i\geq 2a-2+n^2-a = n^2-2+a.\]However, notice that each checker is counted at most four times, because it has at most $4$ surrounding squares. This gives us \[4a\geq\sum_{i=1}^{n^2}C_i\geq n^2-2+a,\]giving $a\geq \frac{n^2-2}{3}$, as desired.

Define a neighbor of a square containing a checker as an adjacent square that does not contain a checker. Clearly no valid configuration exists where a square with a checker has exactly $4$ neighbors. Now in any valid configuration suppose there are $k$ squares with a checker, $a$ of which have $3$ neighbors. Denote $S$ as the sum of the number of neighbors of every square with a checker. On one hand we have $S \ge n^2 - k$, but since $k - a$ checkers have at most $2$ neighbors we also have the bound $3a + 2(k - a) = 2k + a \ge S$. So $3k + a \ge n^2 \implies k \ge \frac{n^2 - a}{3}$. This implies the conclusion when $a \ge 2$. Now if $a = 1$, note that some three squares have checkers that form an L-shape. Then two of the squares with a checker share a neighbor, and we have $3 + 2(k - 1) - 1 \ge S \ge n^2 - k \implies k \ge \frac{n^2}{3} > \frac{n^2 - 2}{3}$. Our proof is complete.

Let $k$ be the number of checkers placed. Call a square black if it contains a checker and white otherwise. For each square $S$, let $f(S)$ be the number of black neighbors of $S$. Our plan is to sum $f$ over all squares so that we can get a lower bound on $k$. Claim: The sum of $f$ over all white squares is at least $n^2 - k$. Proof. Each white square has at least one black neighbor, so the result follows. Claim: The sum of $f$ over all black squares is at least $2k - 2$. Proof. Let $G = (V, E)$ be a graph with its vertices as the $k$ black squares, and connect two vertices by an edge if and only if they're neighbors on the checkerboard. By the handshaking lemma we have \[\sum_{s\text{ black}} f(s) = \sum_{v \in V} \text{deg}(v) = 2|E| \geq 2k - 2,\]where the last inequality follows since $G$ is connected. $\square$ The above two claims imply that $\sum_s f(s) \geq (n^2 - k) + (2k - 2) = n^2 + k - 2$. But each black square in $\sum_s f(s)$ is counted $4$ times, so $\sum_s f(s) = 4k$. Thus \[4k \geq n^2 + k - 2 \implies k \geq \frac{n^2 - 2}{3}\]as desired. $\square$ Remark. The bound can actually be improved to $\frac{n^2 - 1}{3}$, since $n^2 - 2$ is never divisible by $3$.

Let there be $x$ squares with checkers in them. It is clear that all $x$ squares must be connected, and that for the other $n^2-x$ squares we need one of their sides to touch a square with a checker. Therefore, the perimeter of our $x$ squares must be at least $n^2-x$, but if we have $x$ squares our perimeter is at most $2x+2$ (this is from the second condition and that some squares touch sides of the grid). Therefore $$2x+2 \geq n^2-x \implies x \geq \frac{n^2-2}{3}$$done