# Cover a chessboard

Let $$2n\times 2n$$ board. I cover it with dominoes $$1\times 2$$ s.t. every cell is adjacent exactly one cell coverd by a domino. I have to find the maximal number of dominoes that can be placed in this way.

I think that the number is $$\frac { n\cdot (n+1)}{2}$$. I succeed for $$n\in \lbrace 1, 2, 3 \rbrace$$ and I try to prove it by induction.

2 cells are adjacent if they share a common side

• What do you mean by "every cell is ad[j]acent exactly one cell cover[e]d by a domino"? – Dr. Mathva Apr 9 at 10:12
• @Dr. Mathva I added this information – Problemsolving Apr 9 at 10:26
• It may be easier to solve the problem by induction on a $2n\times2m$ board instead. – P. Quinton Apr 9 at 10:39
• @P. Quinton It's my answer right? – Problemsolving Apr 9 at 10:47
• I think that it's is problem 2 form EGMO 2019 (first contest was yesterday). See here artofproblemsolving.com/community/… – richrow Apr 10 at 18:50

To show it is possible to place $$n(n+1)/2$$ dominoes, generalize the domino placements below. • $$x$$ be the number of interior dominoes,
• $$y$$ be the number of dominoes with both halves on the border,
• $$z$$ be the number of dominoes with one half on the border and the other in the interior.
Note that a perimeter domino covers $$4$$ perimeter squares, and a half-interior domino covers at least three perimeter squares. Since there are $$4(2n-1)$$ perimeter squares total, we must have $$4y+3z\le 4(2n-1).$$ Furthermore, an interior domino covers $$8$$ squares, a border domino not on the corner covers $$6$$ squares, an a half-interior domino covers $$7$$ squares. There are at most $$4$$ corner dominoes, which each cover one fewer square. Therefore, $$8x+6y+7z\le 4n^2+4$$ Putting this all together, we get \begin{align} x+y+z &=\frac18(8x+6y+7z)+\frac1{16}(4y+7z)-\frac{5}{16}z \\&\le \frac18(4n^2+4)+\frac1{16}(4(2n-1)) \\&= \frac12n(n+1)+\frac{1}{4} \end{align} Finally, since $$x+y+z$$ is an integer, we further conclude that $$x+y+z\le \left\lfloor\frac12n(n+1)+\frac14\right\rfloor=\frac12n(n+1).$$