Problem: Let $n \ge 3$ be an integer.
Several non-overlapping dominoes are placed on an $n \times n$ board.
The \emph{value} of a row or column is the number of dominoes
that cover at least one cell of that row or column.
A domino configuration is called \emph{balanced} if there exists
some $k \ge 1$ such that every row and column has value $k$.

Prove that a balanced configuration exists for every $n \ge 3$
and find the minimum number of dominoes needed
in such a configuration.

Solution: The answer is $2n/3$ when $n \equiv 0 \pmod 3$, and $2n$ otherwise.

\paragraph{Proof this is best possible.}
To prove these are best possible, assume there are $d$ dominoes.
\begin{claim*}
  In any balanced configuration, we always have $k \cdot 2n = 3d$.
\end{claim*}
\begin{proof}
  Consider counting the number of ordered pairs
  \[ (\text{row or column},
    \text{domino touching at least one cell in that row or column}). \]
  On the one hand, this is equal to $k \cdot 2n$,
  because there are $2n$ choices for the row and column,
  and by the balanced hypothesis, there are $k$ dominoes for that row or column.

  On the other hand, it must be equal to $3d$,
  because for each domino there are either one column and two rows it touches,
  or two columns and one row.

  Hence the result.
\end{proof}

Written another way, we have
\[ d = 2n \cdot \frac{k}{3}. \]
Since $k \ge 1$, the first few possible values of $d$ are $2n/3$, $4n/3$, $2n$, \dots.
So we get a lower bound by taking the first integer in this sequence.

\paragraph{Constructions.}
When $n \equiv 0 \pmod 3$, one takes block-diagonal
copies of the following $3 \times 3$ square with $k = 1$.
\[
  \begin{bmatrix}
    A & A & \\
      &   & B \\
      &   & B
  \end{bmatrix}.
\]

On the other hand, we give below construction for $4 \le n \le 7$
which have $k = 3$ and $2n$ dominoes.
By taking block-diagonal copies of these, we obtain a $k = 3$ construction
using $2n$ dominoes for any value of $n \ge 4$.
\[
  \begin{bmatrix}
    A & A & B & C \\
    D & D & B & C \\
    W & X & Y & Y \\
    W & X & Z & Z
  \end{bmatrix}
  \qquad
  \begin{bmatrix}
    A & A & B & B & C \\
    H & X &   &   & C \\
    H & X &   &   & D \\
    G &   & Y & Y & D \\
    G & F & F & E & E
  \end{bmatrix}
\]
\[
  \begin{bmatrix}
    A & A & B & C & & \\
    D & D & B & C & & \\
    & & W & W & Y & Z \\
    & & X & X & Y & Z \\
    P & Q & & & R & R \\
    P & Q & & & S & S \\
  \end{bmatrix}
  \qquad
  \begin{bmatrix}
    A & A & B & B &   &   & C \\
      & W & W &   &   & X & C \\
      &   & P &   &   & X & D \\
    H &   & P &   &   &   & D \\
    H & Z &   & Q & Q &   &   \\
    G & Z &   &   & Y & Y &   \\
    G &   &   & F & F & E & E
  \end{bmatrix}
\]

\begin{remark*}
  Most of the difficulty of the problem is the construction for $n \in \{5,7\}$.
\end{remark*}