EGMO 2018 Problem 4

A domino is a $1 \times 2$ or $2 \times 1$ tile. Let $n \geq 3$ be an integer. Dominoes are placed on an $n \times n$ board in such a way that each domino covers exactly two cells of the board, and dominoes do not overlap.

The value of a row or column is the number of dominoes that cover at least one cell of this row or column. The configuration is called balanced if there exists some $k \geq 1$ such that each row and each column has a value of $k$.

Prove that a balanced configuration exists for every $n \geq 3$, and find the minimum number of dominoes needed in such a configuration. (Merlijn Staps, The Netherlands)