This is almost the same problem as IMO 1999/3.

I solved only half the problem i.e. without the construction. Denote by $A_{2n}$ the board and attach sides of length $2n$ to all of its sides and also add $4$ corners in order to get a $(2n+2)$x$(2n+2)$ board, which we will call $G_{2n+2}$. Call the set of cells that are covered by a domino or are adjacent to cells that are covered by that particular domino a figure. It is obvious that a figure consists of $8$ cells. The problem can be restated as: find the maximum number of figures that $G_{2n+2}$ can be covered with (without overlapping or any cells of a figure being outside $G_{2n+2}$). Note that every cell of $A_{2n}$ must be covered from the statement of the problem. Consider the configuration with the maximum number of figures on $G_{2n+2}$. Denote by $u_{2n}$ and $v_{2n}$ the number of covered cells and the number of empty cells in that configuration. It is clear that $u_{2n}+v_{2n}=(2n+2)^2$. We will show that $v_{2n} \geq 4n$. Note that empty cells can only be found in the outer sides of $G_{2n+2}$ and that all corners are empty. Let's have a look at an outer side of $G_{2n+2}$, which we will call $a$. We see that a figure has only $2$ orientations for a fixed board and if only $1$ of its cells is in $a$, then the $2$ cells adjacent to the latter must be empty. Similarly if a figure has $2$ of its cells in $a$, then again the $2$ adjacent cells of the latter $2$ must be empty. Thus we conclude that at least half of the cells in $a$ are empty, namely $n+1$. We split $a$ into $a'$ and $2$ of the corners of $G_{2n+2}$. It is evident now that $a'$ contains at least $n-1$ empty cells. So we conclude that $v_{2n} \geq 4*(n-1)+4 = 4n$, as desired. Now we have that $u_{2n} = (2n+2)^2 - v_{2n} \leq (2n+2)^2-4n=4n^2+4n+4$ and so the maximum number of figures is no bigger than $\lfloor\frac{4n^2+4n+4}{8}\rfloor = \lfloor\frac{n^2+n}{2}+\frac{1}{2}\rfloor=\frac{n(n+1)}{2}$.

Here is the other way to do the bound. For each domino, assign weight by adding the number of cells adjacent to that domino (including the domino itself) to the half of the number of such cells which lie on the boundary of the square. The sum of the weight is $4n^2 + \tfrac{8n-4}{2}$ $=4n^2+4n-2$ while each domino has weight at least $8$, except for the (at most four) domino at the corner, which has weight $7$. Thus the number of dominoes is at most $\tfrac{4n^2+4n+2}{8}$ $< \tfrac{n(n+1)}{2}+1$, done.

Another solution: Suppose we have $k$ dominoes placed on the board, and paint all of then black. With this, we have $6k$ black unitary edges painted black. On the other hand, on the border of the $2n \times 2n$, we have at most half of the unitary edges painted black (because each square on the border is neighbor of at least one non black square on the border), and each non black square have at most 1 black edge outside the border of the $2n \times 2n$. Thus, $6k \le (8n)/2+(4n^2-2k)$, which gives $k \le \frac{n(n+1)}{2}$. You can see the example above.

The answer is $\tbinom{n+1}{2}$ and a construction is shown below. For each domino, its aura consists of all the cells which are adjacent to a cell of the domino. There are up to eight squares in each aura, but some auras could be cut off by the boundary of the board, which means that there could be as few as five squares. So we want to estimate how many auras get cut off. We denote by $a$, $b$, $c$, $k$ the number of auras with $5$, $6$, $7$, $8$ cells on the boundary, so we want an upper bound on $a+b+c+k$. Note also that $\boxed{a \le 4}$ since such a cell uses a corner of the grid. [asy][asy] size(11cm); path aura = (1,0)--(2,0)--(2,1)--(3,1)--(3,3)--(2,3)--(2,4)--(1,4)--(1,3)--(0,3)--(0,1)--(1,1)--cycle; picture aura_up(pen fill) { picture pic = new picture; fill(pic, aura, fill); draw(pic, (1,1)--(2,1), lightgrey ); draw(pic, (1,3)--(2,3), lightgrey ); draw(pic, (0,2)--(3,2), lightgrey ); draw(pic, (1,1)--(1,3), lightgrey ); draw(pic, (2,1)--(2,3), lightgrey ); draw(pic, aura, blue+1.25); return pic; } picture aura_right(pen fill) { return shift(0,3) * rotate(-90) * aura_up(fill); } add(shift(-1,-1)*aura_up(palegreen)); add(shift(-1,3)*aura_up(palegreen)); add(shift(-1,7)*aura_up(palegreen)); add(shift(1,1)*aura_up(palegreen)); add(shift(1,5)*aura_up(palegreen)); add(shift(3,3)*aura_up(palegreen)); add(shift(6,3)*aura_up(palegreen)); add(shift(8,1)*aura_up(palegreen)); add(shift(8,5)*aura_up(palegreen)); add(shift(10,-1)*aura_up(palegreen)); add(shift(10,3)*aura_up(palegreen)); add(shift(10,7)*aura_up(palegreen)); add(shift(4,6)*aura_right(palered)); add(shift(2,8)*aura_right(palered)); add(shift(6,8)*aura_right(palered)); /* add(shift(0,10)*aura_right(palered)); add(shift(4,10)*aura_right(palered)); add(shift(8,10)*aura_right(palered)); */ add(shift(4,1)*aura_right(palered)); add(shift(2,-1)*aura_right(palered)); add(shift(6,-1)*aura_right(palered)); add(shift(0,-3)*aura_right(palered)); add(shift(4,-3)*aura_right(palered)); add(shift(8,-3)*aura_right(palered)); draw(shift(0,-2)*scale(12)*unitsquare, black+2); path cell = shift(16,-2)*unitsquare; for (int i = 0; i <= 11; ++i) { for (int j = 0; j <= 11; ++j) { if (max(abs(i-5.5), abs(j-5.5)) == 5.5) filldraw(shift(i,j)*cell, paleblue, grey); /* else if (max(abs(i-5.5), abs(j-5.5)) == 3.5) filldraw(shift(i,j)*cell, paleblue, grey); else if (max(abs(i-5.5), abs(j-5.5)) == 1.5) filldraw(shift(i,j)*cell, paleblue, grey); */ else draw(shift(i,j)*cell, grey); } } [/asy][/asy] The big observation about the auras on the edge: Claim: The auras of type $a$, $b$, $c$ have $4$, $4$, $3$ cells on the boundary of the grid (i.e.\ the $4(2n-1)$ cells touching an edge of the board). Consequently, we have a bound $4a + 4b + 3c \le 4(2n-1)$. On the other hand, we obviously have $5a + 6b + 7c + 8k = 4n^2$. Therefore, \begin{align*} 4n^2 + 2(2n-1) &\ge (5a+6b+7c+8k) + (2a+2b+1.5c) \\ &= 8(a+b+c+k) + 0.5c - a \\ &\ge 8(a+b+c+k) + 0 - 4 \\ \implies \frac{n(n+1)}{2} + \frac 14 &\ge a+b+c+k \end{align*}which implies the desired bound after taking the floor of left-hand side.

Another solution which is longer:

How would you write up a construction for this solution (or any other solution)? It probably wouldn't suffice to just give an example on an olympiad, right?

mwomwo wrote:

How would you write up a construction for this solution (or any other solution)? It probably wouldn't suffice to just give an example on an olympiad, right? Here's a but more explanation to the construction, in general. Clearly, the problem is equivalent to tiling the $2n\times 2n$ grid with 8-piece tiles, which are a domino surrounded by the 6 squares a distance 1 away from a square of the domino. Note that we must cover the entire grid, but we are allowed to ``cut off'' some blocks on the edges. Consider the following tiling $S$, which is clearly generalizable for any even $n$:

We are basically filling concentric squares with as many tiles as we can. Note that $S$ contains $n^2/2$ tiles. The problem is that there are little holes on the boundary. For $n$ even, simply shift $S$ to the left by 1 and fill in these holes with extra tiles. This produces a valid tiling. Note that since we are adding $n/2$ tiles, there will be a total of $\tfrac{n^2}{2} + \tfrac{n}{2} = \tfrac{n(n+1)}{2}$ tiles. For $n$ odd, just take $S$ for $n+1$ (which is even), but remove the first and last columns, as well as the last two rows. This produces a valid tiling for odd $n$. Note that since we are removing $\tfrac{n+1}{2}$ tiles, there will be a total of $\tfrac{(n+1)^2}{2} - \tfrac{n+1}{2} = \tfrac{n(n+1)}{2}$ tiles. Therefore, we can produce a valid configuration, and it uses $\tfrac{n(n+1)}{2}$ tiles.

Remark: Similar to CantonMathGuy. Kinda motivated by 2019 CMO 3 but maybe I'm just weird. Color in rings of even side length, as shown in CantonMathGuy's diagram for $n = 5$: [asy][asy] int n = 5; for (int i = -(2*n-1); i <= 2*n-1; i += 2) for (int j = -(2*n-1); j <= 2*n-1; j += 2) { filldraw((i-1,j-1)--(i-1,j+1)--(i+1,j+1)--(i+1,j-1)--cycle, (max(abs(i), abs(j)) - 2*n) % 4 == 3 ? gray(0.6) : white); } [/asy][/asy] For each domino, let the set of six distinct squares bordering it be called its bubblespace. Clearly, no square can belong to the bubblespace of two dominoes. Also, note that in this diagram, no matter where we place a domino, four squares in its bubblespace will be colored. It is easy to count that there are \[(8n - 4) + (8n - 12) + \ldots + 4 = 2n(n+1)\]colored squares and since no two bubblespaces can intersect, there must be at most $\tfrac{2n(n+1)}{8} = \tfrac{n(n+1)}{2}$ dominoes as desired. Constructions can be found in other posts above.

The answer is $\frac{n^2 + n}{2}$. First we define each cell with grid coordinates $(i,j)$ for $1\le i \le 2n$ and $1\le j \le 2n$ as normal. Define a ring to be a set of cells $(i,j)$ such that $\min(\min(i - 1, 2n - i) , \min(j-1, 2n - j))$ takes a fixed value and call a ring even if this value is even. For each even ring, place a number on each cell in the following way: Start from the top left and label it with $1$. Go right until you hit a corner, then go down until you hit a corner, then go left until you hit a corner, and then go up until you hit the final cell of the ring. As you do this, label the cells $1 \to 2 \to \cdots \to 4r - 4$, where $r$ is the side length of the ring. The construction is given by placing a domino between every cell labelled $1\pmod 4$ and its neighboring cell labeled $2\pmod 4$. This gives a total of\[(2n-1) + (2n-5) + \cdots = 1 + 2 + \cdots + n = \frac{n ^2 + n}{2}\]dominos. An example for $n = 6$ is shown below (I'll edit this in later). Now we prove the bound. Define a function $f$ from the set $\{0,1,\ldots, 2n + 1\}$ to itself where $f(i,j) = 0$ if either one of $i,j$ is in $\{0,2n + 1\}$ or there is no domino on cell $(i,j)$ and $f(i,j) = 1$ if there is a domino on cell $(i,j)$. The problem condition is equivalent to\[ f(i-1,j) + f(i,j-1) + f(i+1,j) + f(i,j+1) = 1\forall 1\le i \le 2n, 1\le j \le 2n\]and we have to prove that $\sum_{1\le i,j \le 2n } f(i,j) \le n^2 + n$, as it is equal to twice the number of dominoes. Let $a$ be the sum of $f$'s over all the cells with exactly one coordinate in $\{1,2n\}$ (in the outermost ring but not in a corner) and $b$ be sum of $f$ over all cells with both coordinates $\{1,2n\}$ (i.e. the corner cells). Consider summing the above equation over all $1\le i,j \le 2n$. It's clear that each $(i,j)$ with $2\le i,j \le 2n - 1$ is counted four times, each $(i,j)$ with exactly one coordinate in $\{1,2n\}$ is counted three times, and each corner square is counted twice. Hence the sum is equal to\[ 4\sum_{1\le i,j \le 2n } f(i,j) - (a + 2b) ,\]which must be equal to $4n^2$. Claim: $a + 2b \le 4n$. Proof: Again, number the cells of the outermost ring as described in the construction. Consider the $4n$ pairs $(1 \mid 3), (5 \mid 7), \ldots, (4n-3 \mid 4n - 1), (4n-1\mid 4n+1), (4n+3\mid 4n +5), \ldots, (8n-9\mid 8n-7), (8n-5\mid 1), (2n \mid 2n+2), (2n + 2 \mid 2n + 4) \ldots, (6n - 4\mid 6n - 2), \ldots, (6n-2\mid 6n), \ldots, (2n-2\mid 2n)$ (where the next even number after $8n - 4$ is $2$). Notice that each pair has at most one domino in it and the union of these pairs covers $a + 2b$ exactly. Hence $a + 2b \le 4n$. $\square$ Now, we have\[ 4n^2 = 4 \sum_{1\le i,j \le 2n} f(i,j) - (a + 2b) \ge 4 \sum_{1 \le i,j \le 2n} f(i,j) - 4n ,\]implying that $\sum_{1\le i,j \le 2n} f(i,j) \le n^2+ n$, as desired.