(1) If $n=3m$, then the smallest possible balance is $k=1$ and you need $2n/3$ dominoes. (2) If $n$ is not a multiple of $3$, then the smallest possible balance is $k=3$ and you need $2n$ dominoes. If every row and every column has value $k$, then the sum of all values (over all rows and all columns) is $S=2nk$. On the other hand, every domino contributes exactly $3$ to the total sum $S$; hence if there are $d$ dominoes then $S=3d$. This yields $S=2nk=3d$. (1) If $n$ is a multiple of $3$, then $d=2nk/3\ge 2n/3$. (2) If $n$ is not a multiple of $3$, then $d=2nk/3\ge 2n$. For $n=3$, use the construction (x= empty spot): xAA Bxx Bxx (For $n$ a multiple of $3$, put copies of these 3x3 squares along the diagonal.) For $n=4$, use the construction AACD BBCD EFGG EFHH For $n=5$, use the construction xAABC DDxBC ExFFG ExHxG IIHJJ For $n=6$, use the construction AAxxGH BBxxGH CCxxIJ xxDDIJ xxEEKL xxFFKL For $n=7$, use the construction (For $n\ge8$ and not a multiple of $3$, put one copy of the 4x4, 5x5, 6x6, 7x7 square together with several copies of the 4x4 square along the diagonal.)

test20 wrote: If $n=3m$, then the smallest possible balance is $k=2$ and you need $4n$/3 dominoes. If $n$ is not a multiple of $3$, then the smallest possible balance is $k=3$ and you need $2n$ dominoes. I think the answer for $3 \mid n$ should be $2n/3$, not $4n/3$, with $k=1$. Anyways, for both parts, we have $2nk = 3 \# \text{dominoes}$ which implies the right lower bounds. Still trying to find the construction for $3 \nmid n$.

test20 wrote: For $n=3$, use the construction (x= empty spot): AAB DxB DCC actually try AAx xxB xxB

test20 wrote: (1) If $n=3m$, then the smallest possible balance is $k=2$ and you need $2n/3$ dominoes. (2) If $n$ is not a multiple of $3$, then the smallest possible balance is $k=3$ and you need $2n$ dominoes. If every row and every column has value $k$, then the sum of all values (over all rows and all columns) is $S=2nk$. On the other hand, every domino contributes exactly $3$ to the total sum $S$; hence if there are $d$ dominoes then $S=3d$. This yields $S=2nk=3d$. (1) If $n$ is a multiple of $3$, then $d=2nk/3\ge 2n/3$. (2) If $n$ is not a multiple of $3$, then $d=2nk/3\ge 2n$. For $n=3$, use the construction (x= empty spot): AAB DxB DCC (For $n$ a multiple of $3$, put copies of these 3x3 squares along the diagonal.) For $n=4$, use the construction AACD BBCD EFGG EFHH For $n=5$, use the construction xAABC DDxBC ExFFG ExHxG IIHJJ For $n=6$, use the construction AAxxGH BBxxGH CCxxIJ xxDDIJ xxEEKL xxFFKL For $n=7$, use the construction (For $n\ge8$ and not a multiple of $3$, put one copy of the 4x4, 5x5, 6x6, 7x7 square together with several copies of the 4x4 square along the diagonal.) Here is the $n=7$ example: AABB00C 0D00EEC 0DFF00G H000K0G H000KL0 MNN00L0 M00QQPP

Somewhat regular construction for $n = 7$: fill the topmost row and leftmost column, except for the top-left cell, with three dominoes each; divide the remaining $6 \times 6$ grid in four $3 \times 3$ subgrids and fill each of them with the $k = 1$ construction for $n = 3$.

as long as we have construction for 4,5,6,7 we can: for $n=6k+4$ (put k $6\times6$ squares and 1 $4\times4$ on the diagonal); for $n=6k+7$ (similarly put k of $6\times 6$ and 1 of $7\times7$); for $n=6k+5$ (k of $6\times 6$ and 1 of $5\times5$); for $n=6k+8$ (k of $6\times6$ and 2 of $4\times4$ on the diagonal);

The construction reminds me a recent APMO problem lol.

This year APMO? Let's do not discuss it.

Construction for $n$ multiple of $3$ is easy, and here's my construction (generalizable easily) for $n=7$. AABBCXX XDDXCEX XXFFXEG HXXIIXG HXXXJJK LMXXXXK LMXXXNN

Firstly by counting the sum of the values across all the rows and columns we see: $$2nk=3d$$Where $d$ is the number of dominoes. For $3 \vert n$ we show $k=1$ suffices with the follow construction using $\frac{2n}{3}$ dominoes: For $3 \not \vert n$ we see $k\geq 3$ by divisibility. We show $k=3$ suffices. For $n=4,5,7$ we describe the construction explicitely: Then for $n \geq 8$ we go by induction. If $n \equiv 2 \pmod{3}$ then we place a $4\text{x}4$ grid in the top-left corner and a $(n-4) \text{x} (n-4)$ grid in the bottom-right corner. We can do this as $3 \not \vert n-4$ and $n-4 \geq 4$. We see each row, column has value $3$ as desired. If $n \equiv 1 \pmod{3}$ then we place a $5\text{x}5$ grid in the top-left corner and a $(n-5) \text{x} (n-5)$ grid in the bottom-right corner. We can do this as $3 \not \vert n-5$ and $n-5 \geq 5$ (as $n \geq 10$). We see each row, column has value $3$ as desired. So we can construct the grid for all $n$.

The answer is $\frac{2n}{3}$ if $3\mid n$ and $2n$ if else. First, we prove that these are lower bounds. For each row or column, count the number of dominoes that lie on it. Because the configuration is balanced, this is $k$ for each row or column, so the total sum is $2nk$. Meanwhile, each domino is counted in this sum exactly $3$ times (once for the row/column which is is completely contained within, once each for the rows/columns which it only hits once), so the number of dominoes is $\frac{2nk}{3}$. When $3\mid n$, we have $k\geq1$ so $\frac{2nk}{3}\geq\frac{2n}{3}$. When $3\nmid n$, $k\geq3$ for divisibility, so $\frac{2nk}{3}\geq2n$. Now, we construct these bounds. For $3\mid n$, do the following: [asy][asy] size(6cm); real d = 0.1; int n = 6; path rect(int a, int b, int x, int y) { return (a-1+d,b-1+d)--(x-d,b-1+d)--(x-d,y-d)--(a-1+d,y-d)--cycle; } for (int i = 0; i <= n; ++i) { draw((i,0)--(i,n)); draw((0,i)--(n,i)); } fill(rect(1,4,1,5),red); fill(rect(2,6,3,6),red); fill(rect(4,1,4,2),red); fill(rect(5,3,6,3),red); [/asy][/asy] (continued in a block-diagonal repetition of the formation $\frac{n}{3}$ times). So it suffices to show that every $n\geq3$ not divisible by $3$ has a balanced configuration with $2n$ dominoes. We go further and show that every $n\geq4$ except $6$ has a balanced configuration with $2n$ dominoes (equivalently with $k=3$). First, let us construct it for $n=4,5,7$: [asy][asy] size(4cm); real d = 0.1; int n = 4; path rect(int a, int b, int x, int y) { return (a-1+d,b-1+d)--(x-d,b-1+d)--(x-d,y-d)--(a-1+d,y-d)--cycle; } for (int i = 0; i <= n; ++i) { draw((i,0)--(i,n)); draw((0,i)--(n,i)); } fill(rect(1,1,1,2),red); fill(rect(2,1,2,2),red); fill(rect(1,3,2,3),red); fill(rect(1,4,2,4),red); fill(rect(3,1,4,1),red); fill(rect(3,2,4,2),red); fill(rect(3,3,3,4),red); fill(rect(4,3,4,4),red); [/asy][/asy] [asy][asy] size(5cm); real d = 0.1; int n = 5; path rect(int a, int b, int x, int y) { return (a-1+d,b-1+d)--(x-d,b-1+d)--(x-d,y-d)--(a-1+d,y-d)--cycle; } for (int i = 0; i <= n; ++i) { draw((i,0)--(i,n)); draw((0,i)--(n,i)); } fill(rect(1,1,1,2),red); fill(rect(1,3,1,4),red); fill(rect(1,5,2,5),red); fill(rect(2,2,3,2),red); fill(rect(2,3,3,3),red); fill(rect(3,1,4,1),red); fill(rect(4,3,5,3),red); fill(rect(4,4,4,5),red); fill(rect(5,4,5,5),red); fill(rect(5,1,5,2),red); [/asy][/asy] [asy][asy] size(7cm); real d = 0.1; int n = 7; path rect(int a, int b, int x, int y) { return (a-1+d,b-1+d)--(x-d,b-1+d)--(x-d,y-d)--(a-1+d,y-d)--cycle; } for (int i = 0; i <= n; ++i) { draw((i,0)--(i,n)); draw((0,i)--(n,i)); } fill(rect(1,2,1,3),red); fill(rect(1,5,1,6),red); fill(rect(1,7,2,7),red); fill(rect(2,1,2,2),red); fill(rect(2,4,2,5),red); fill(rect(3,1,4,1),red); fill(rect(3,4,4,4),red); fill(rect(3,6,3,7),red); fill(rect(4,5,5,5),red); fill(rect(5,2,6,2),red); fill(rect(5,3,5,4),red); fill(rect(6,1,7,1),red); fill(rect(6,3,7,3),red); fill(rect(7,6,7,7),red); [/asy][/asy] Now, I claim that the set of $n$ that have a balanced configuration with $k=3$ is closed under addition. Indeed, if $n_1$ and $n_2$ have this property, then just construct $n_1+n_2$ by appending the construction for $n_2$ to that of $n_1$ in a block-diagonal fashion. As an example, here is the construction for $11=4+7$: [asy][asy] size(11cm); real d = 0.1; int n = 11; path rect(int a, int b, int x, int y) { return (a-1+d,b-1+d)--(x-d,b-1+d)--(x-d,y-d)--(a-1+d,y-d)--cycle; } for (int i = 0; i <= n; ++i) { draw((i,0)--(i,n)); draw((0,i)--(n,i)); } fill(rect(1,8,1,9),red); fill(rect(2,8,2,9),red); fill(rect(1,10,2,10),red); fill(rect(1,11,2,11),red); fill(rect(3,8,4,8),red); fill(rect(3,9,4,9),red); fill(rect(3,10,3,11),red); fill(rect(4,10,4,11),red); fill(rect(5,2,5,3),red); fill(rect(5,5,5,6),red); fill(rect(5,7,6,7),red); fill(rect(6,1,6,2),red); fill(rect(6,4,6,5),red); fill(rect(7,1,8,1),red); fill(rect(7,4,8,4),red); fill(rect(7,6,7,7),red); fill(rect(8,5,9,5),red); fill(rect(9,2,10,2),red); fill(rect(9,3,9,4),red); fill(rect(10,1,11,1),red); fill(rect(10,3,11,3),red); fill(rect(11,6,11,7),red); [/asy][/asy] This works because each of the first $n_1$ rows and columns still only have $3$ dominoes, and same with each of the last $n_2$ rows and columns. Since $4$ and $5$ have this property, by the Chicken McNugget Theorem, all integers larger than $4\cdot5-4-5=11$ have this property. So it suffices to check $4,5,7,8,9,10,11$ have this property. We have already constructed $4,5,7$ and have $8=4+4,9=4+5,10=5+5,11=4+7$, so our claim is true. So a construction for the lower bound provided exists and thus the minimum is indeed as claimed at the beginning.

Nice problem. We claim that such a construction always exists, and the minimum number of dominoes required is: 1. $2n/3$ if $3 | n$ 2. $2n$ otherwise. If we have a balanced configuration each for $a \times a$ and $b \times b$ boards such that both the configurations have the same value of $k$, then we have a balanced configuration of an $(a+b) \times (a+b)$ board with the same value of $k$. Place the dominoes according to the $a \times a$ balanced configuration in the square with opposite corners $(1,1)$ and $(a,a)$ and according to the $b \times b$ balanced configuration in the square with opposite corners $(a+1),(a+1)$ and $(a+b),(a+b)$, leaving the rest of the $(a+b) \times (a+b)$ board empty. Constructions of balanced configurations for $n = 3$ with $k = 1$ and $n = 4, 5, 7$ with $k = 3$ are already given in the above solutions. Using these constructions, we can construct balanced configurations with $k = 1$ if $3 | n$, and $k = 3$ otherwise. Let us count the sum of the values of the rows and columns of a balanced $n \times n$ configuration in 2 ways. Let $m$ be the number of dominoes used in the configuration. Counting by row and column, the sum comes to be $2nk$, and counting by domino, as each domino contributes $3$ to the sum, the sum comes to be $3m$. Thus, $3m = 2nk$. 1. If $3 | n$, the minimum values of $k$ is $1$. This gives minimum $m = 2n/3$. 2. Otherwise, as $3$ must divide the RHS, the minimum value of $k$ is $3$. This gives minimum $m = 2n$.

As previously stated: test20 wrote: If every row and every column has value $k$, then the sum of all values (over all rows and all columns) is $S=2nk$. On the other hand, every domino contributes exactly $3$ to the total sum $S$; hence if there are $d$ dominoes then $S=3d$. This yields $S=2nk=3d$. (1) If $n$ is a multiple of $3$, then $d=2nk/3\ge 2n/3$. (2) If $n$ is not a multiple of $3$, then $d=2nk/3\ge 2n$. We proceed by showing that this minimum can be reached by constructing inductively for three separate cases as shown in the images below. For the cases where $n$ is not divisible by $3$, we always add two dominoes in the bottom-right $3\times 3$ square, and "move" (erase and duplicate) the dominoes from the top-right and bottom-left $3\times 3$ square from the previous step. (red domino: erased from previous step; green domino: added in this step)

Here is a solution with a different construction for $3 \nmid n$, which looks nice. Let $d$ be the number of dominoes on the board. Lemma 1: Any balanced domino configuration satisfies $2nk=3d$. Proof: Consider the sum of the values of each row and column, which totals to $2nk$. Each domino on the board adds $3$ to this sum, so it must be equal to $3d$. $\square$ To minimize $d$ it suffices to minimize $k$. We will first prove the cases $n=3$ and $n=4$. The former can be accomplished like so: [asy][asy] size(2cm); draw((0,0)--(3,0)); draw((0,1)--(3,1)); draw((0,2)--(3,2)); draw((0,3)--(3,3)); draw((0,0)--(0,3)); draw((1,0)--(1,3)); draw((2,0)--(2,3)); draw((3,0)--(3,3)); filldraw((0,2)--(0,3)--(2,3)--(2,2)--cycle, grey); filldraw((2,0)--(3,0)--(3,2)--(2,2)--cycle, grey); [/asy][/asy] This is clearly the minimum valued tiling for $n=3$, with $k=1$. For future reference, call this specific $3\times 3$ sub-grid configuration good. The $n=4$ case can be accomplished like so: [asy][asy] size(2cm); add(grid(4,4)); filldraw((0,0)--(1,0)--(1,2)--(0,2)--cycle,grey); filldraw((1,0)--(2,0)--(2,2)--(1,2)--cycle,grey); filldraw((2,2)--(3,2)--(3,4)--(2,4)--cycle,grey); filldraw((3,2)--(4,2)--(4,4)--(3,4)--cycle,grey); filldraw((0,2)--(2,2)--(2,3)--(0,3)--cycle,grey); filldraw((0,3)--(2,3)--(2,4)--(0,4)--cycle,grey); filldraw((2,0)--(4,0)--(4,1)--(2,1)--cycle,grey); filldraw((2,1)--(4,1)--(4,2)--(2,2)--cycle,grey); [/asy][/asy] This is also the minimum valued tiling for $n=4$, with $k=3$. As Lemma 1 implies $3 \mid k$ for $n=4$, no smaller $k$ value exists. For future reference, call this specific $4\times 4$ tiling great. We will split the rest into two cases: $3\mid n$ and $3\nmid n$. If $3 \mid n$, I claim that a balanced configuration exists and has a minimum value of $k=1$, which gives $d=2n/3$. This is achieved by the following construction. Let $n=3m$. Reconsider the $n \times n$ board as an $m \times m$ board of $3 \times 3$ sub-grids. Then tile each of the $m$ sub-grids along the diagonal as good. It is easy to check that this construction satisfies the claim. If $3 \nmid n$, I claim that a balanced configuration exists and has a minimum value of $k=3$, which gives $d=2n$. Note that if this is true, then it must be the minimum because Lemma 1 implies that $3 \mid k$. Again proceed constructively. We will split this case this into two more cases, first proving the claim when $n$ is odd. Tile the central $3\times 3$ sub-grid as good and then split the rest of the grid into four quadrants, as shown (here is $n=11$, though clearly it is possible for any odd $n>3$). [asy][asy] size(4cm); add(grid(11,11)); filldraw((4,6)--(6,6)--(6,7)--(4,7)--cycle, grey); filldraw((6,4)--(6,6)--(7,6)--(7,4)--cycle, grey); draw((4,4)--(4,7)--(7,7)--(7,4)--cycle, linewidth(1.5)); draw((6,7)--(6,11),linewidth(1.5)); draw((7,5)--(11,5),linewidth(1.5)); draw((5,4)--(5,0),linewidth(1.5)); draw((4,6)--(0,6),linewidth(1.5)); [/asy][/asy] Now tile the upper-left quadrant with $(n-1)/2$ dominoes like so: starting in the bottom left corner with a vertical domino, continuing to place dominoes in a staircase fashion until the top of the grid is reached, and finishing with a horizontal domino. [asy][asy] size(4cm); add(grid(11,11)); filldraw((4,6)--(6,6)--(6,7)--(4,7)--cycle, grey); filldraw((6,4)--(6,6)--(7,6)--(7,4)--cycle, grey); draw((4,4)--(4,7)--(7,7)--(7,4)--cycle, linewidth(1.5)); draw((6,7)--(6,11),linewidth(1.5)); draw((7,5)--(11,5),linewidth(1.5)); draw((5,4)--(5,0),linewidth(1.5)); draw((4,6)--(0,6),linewidth(1.5)); filldraw((0,6)--(1,6)--(1,8)--(0,8)--cycle, grey); filldraw((1,7)--(2,7)--(2,9)--(1,9)--cycle, grey); filldraw((2,8)--(3,8)--(3,10)--(2,10)--cycle, grey); filldraw((3,9)--(4,9)--(4,11)--(3,11)--cycle, grey); filldraw((4,10)--(6,10)--(6,11)--(4,11)--cycle,grey); [/asy][/asy] Rotate this quadrant about the center of the grid to obtain the tilings for each of the other quadrants. One can verify that this construction satisfies all of the claims. This proves the odd case. [asy][asy] size(4cm); add(grid(11,11)); filldraw((4,6)--(6,6)--(6,7)--(4,7)--cycle, grey); filldraw((6,4)--(6,6)--(7,6)--(7,4)--cycle, grey); filldraw((0,6)--(1,6)--(1,8)--(0,8)--cycle, grey); filldraw((1,7)--(2,7)--(2,9)--(1,9)--cycle, grey); filldraw((2,8)--(3,8)--(3,10)--(2,10)--cycle, grey); filldraw((3,9)--(4,9)--(4,11)--(3,11)--cycle, grey); filldraw((4,10)--(6,10)--(6,11)--(4,11)--cycle,grey); filldraw((7,0)--(8,0)--(8,2)--(7,2)--cycle, grey); filldraw((8,1)--(9,1)--(9,3)--(8,3)--cycle, grey); filldraw((9,2)--(10,2)--(10,4)--(9,4)--cycle, grey); filldraw((10,3)--(11,3)--(11,5)--(10,5)--cycle, grey); filldraw((5,0)--(7,0)--(7,1)--(5,1)--cycle, grey); filldraw((0,4)--(1,4)--(1,6)--(0,6)--cycle, grey); filldraw((3,0)--(5,0)--(5,1)--(3,1)--cycle, grey); filldraw((2,1)--(4,1)--(4,2)--(2,2)--cycle, grey); filldraw((1,2)--(3,2)--(3,3)--(1,3)--cycle, grey); filldraw((0,3)--(2,3)--(2,4)--(0,4)--cycle, grey); filldraw((9,7)--(11,7)--(11,8)--(9,8)--cycle, grey); filldraw((8,8)--(10,8)--(10,9)--(8,9)--cycle, grey); filldraw((7,9)--(9,9)--(9,10)--(7,10)--cycle, grey); filldraw((6,10)--(8,10)--(8,11)--(6,11)--cycle, grey); filldraw((10,5)--(11,5)--(11,7)--(10,7)--cycle, grey); draw((6,7)--(6,11),linewidth(1.5)); draw((7,5)--(11,5),linewidth(1.5)); draw((5,4)--(5,0),linewidth(1.5)); draw((4,6)--(0,6),linewidth(1.5)); draw((4,4)--(4,7)--(7,7)--(7,4)--cycle, linewidth(1.5)); [/asy][/asy] Now, if $n$ is not odd, then let $2^j$ be the greatest power of two that divides $n$, and let $n=c\cdot 2^j$. Clearly $c$ is odd; if $c=1$, then $n$ is a power of two and we may reconsider it as a $2^{j-2}\times 2^{j-2}$ grid of $4\times 4$ sub-grids. Then, tiling so that each $4\times 4$ sub-grid on the diagonal is great, we arrive at the desired construction. If instead $c>1$, then we may view the grid as a $2^{j}\times 2^{j}$ grid of $c\times c$ sub-grids. As we have shown, it is possible to tile a $c\times c$ grid such that it is balanced and has value $3$. Doing so for each of the $c\times c$ sub-grids along the diagonal produces the desired minimal balanced configuration. This exhausts all cases, so we conclude that $d=2n/3$ is the minimum for $3 \mid n$ and $d=2n$ is the minimum for $3 \nmid n$. $\blacksquare$

The key observation is that each tile contributes exactly $3$ to the sum of the values of all rows and column. Hence if there are $T$ tiles, we have $2nk = 3T\implies T = \frac{2}{3}nk$. Since this is an integer, we obtain a minimum of $k=1\implies T = \frac{2}{3}n$ when $n$ is a multiple of $3$ and $T = 3\implies k = 2n$ otherwise. For $3 | n$, repeatedly concatenate the following construction for $n=3$ along the diagonal: For $n$ not a multiple of $3$, consider the following constructions for $n=4,5,7$: Since $8=4+4$, $10=5+5$, and $11=4+7$, by the Chicken McNugget Theorem we can form a valid construction for all $n$ that is not a multiple of $3$ by concatenating copies of the above three constructions along the diagonal.

My most intense write-up to date. Took me around a hour and a half. We will claim that the minimum number of dominoes needed for a balanced configuration is \[ \begin{cases} \frac{2n}{3} &\text{for } n\equiv 0\pmod{3} \\ 2n &\text{for } n\not\equiv 0\pmod{3} \end{cases} \] It is easy to see that if $n=3$ then the configuration is possible with the value being $k=1$. Then if $3\mid n$ we can string together $\frac{n}{3}$ of these $3\times 3$ grids along the diagonal. [asy][asy] size(5cm); int n = 3; real d = 0.1; path rect(int a, int b, int x, int y) { return (a+d,b+d)--(x-d,b+d)--(x-d,y-d)--(a+d,y-d)--cycle; } for (int i = 0; i <= n; ++i) { draw((i,0)--(i,n)); draw((0,i)--(n,i)); } fill(rect(0, 0, 1, 2), black); fill(rect(1, 2, 3, 3), black); [/asy][/asy] This is when $n=3$ and when $n=6$ it would look something like [asy][asy] size(5cm); int n = 6; real d = 0.1; path rect(int a, int b, int x, int y) { return (a+d,b+d)--(x-d,b+d)--(x-d,y-d)--(a+d,y-d)--cycle; } for (int i = 0; i <= n; ++i) { draw((i,0)--(i,n)); draw((0,i)--(n,i)); } fill(rect(0, 3, 1, 5), black); fill(rect(1, 5, 3, 6), black); fill(rect(3, 0, 4, 2), black); fill(rect(4, 2, 6, 3), black); [/asy][/asy] Notice that when $n=4$ the configuration will look like [asy][asy] size(5cm); int n = 4; real d = 0.1; path rect(int a, int b, int x, int y) { return (a+d,b+d)--(x-d,b+d)--(x-d,y-d)--(a+d,y-d)--cycle; } for (int i = 0; i <= n; ++i) { draw((i,0)--(i,n)); draw((0,i)--(n,i)); } fill(rect(0, 2, 1, 4), black); fill(rect(1, 2, 2, 4), black); fill(rect(2, 3, 4, 4), black); fill(rect(2, 2, 4, 3), black); fill(rect(0, 0, 2, 1), black); fill(rect(0, 1, 2, 2), black); fill(rect(2, 0, 3, 2), black); fill(rect(3, 0, 4, 2), black); [/asy][/asy] Claim 1. A configuration is achievable for all the primes. Proof. We will use induction to prove this. The base cases are $n=3, 4, 5, 7$. We have already proved $n=3, 4$. It remains to prove for $n=5, 7$. For $n=5$, we can have [asy][asy] size(5cm); int n = 5; real d = 0.1; path rect(int a, int b, int x, int y) { return (a+d,b+d)--(x-d,b+d)--(x-d,y-d)--(a+d,y-d)--cycle; } for (int i = 0; i <= n; ++i) { draw((i,0)--(i,n)); draw((0,i)--(n,i)); } fill(rect(0, 0, 1, 2), black); fill(rect(0, 2, 2, 3), black); fill(rect(0, 3, 1, 5), black); fill(rect(1, 4, 3, 5), black); fill(rect(1, 0, 3, 1), black); fill(rect(2, 2, 3, 4), black); fill(rect(3, 1, 4, 3), black); fill(rect(3, 3, 5, 4), black); fill(rect(3, 4, 5, 5), black); fill(rect(4, 0, 5, 2), black); [/asy][/asy] For $n=7$ we have [asy][asy] size(5cm); int n = 7; real d = 0.1; path rect(int a, int b, int x, int y) { return (a+d,b+d)--(x-d,b+d)--(x-d,y-d)--(a+d,y-d)--cycle; } for (int i = 0; i <= n; ++i) { draw((i,0)--(i,n)); draw((0,i)--(n,i)); } fill(rect(0, 0, 2, 1), black); fill(rect(0, 1, 2, 2), black); fill(rect(0, 6, 2, 7), black); fill(rect(2, 0, 4, 1), black); fill(rect(2, 2, 3, 4), black); fill(rect(2, 4, 3, 6), black); fill(rect(4, 0, 6, 1), black); fill(rect(5, 1, 6, 3), black); fill(rect(5, 5, 6, 7), black); fill(rect(6, 1, 7, 3), black); fill(rect(6, 3, 7, 5), black); fill(rect(6, 5, 7, 7), black); fill(rect(3, 3, 5, 4), black); fill(rect(3, 4, 5, 5), black); [/asy][/asy] Notice that in each of these configurations, the value is $k=3$. Now in order to prove for the primes, let $p$ be the prime that we are trying to reach a construction for and let two numbers $a$ and $b$ such that $a+b=p$ and $3\nmid a, b$. If $p>7$ it is easy to see that such $a$ and $b$ exist. For example it is easy to see that one of the pairs $(4, p-4), (5, p-5)$ works. Then we can string together the $a\times a$ board and the $b\times b$ board along the diagonal and we would have a valid configuration. $\blacksquare$ Claim 2. All composite $n$ work as well. Proof. Since all prime $n$ work, if $n>6$ is composite, then we can pick some $p>2$ such that $p\mid n$ and string together $p\times p$ boards along the diagonal. $\blacksquare$ Now to prove that this is the minimum possible value of a balanced configuration, the following lemma is presented. Lemma 1. $3\mid 2kn$. Proof. If we consider the sum of all the values of the rows and columns, then every time we add a domino it will increase this sum by exactly $3$. Thus we must have $3\mid 2kn$. $\blacksquare$ Using this lemma we can prove that when $n=4$ this is the minimum value satisfying this configuration. If $n\equiv 0\pmod{3}$ it is easy to see that $k=1$ is the minimum and since this is acheivable, we are done for this case. It is easy to see that we must need $\frac{2n}{3}$ dominoes for $3\mid n$. If $n\not\equiv 0\pmod{3}$ then notice that the minimum $k$ is $k=3$ but since we are stringing together two boards that both have value of $3$ and since they're on the diagonals, the value of the final board will also have a value of $3$. Then the dominoes needed is $2n$. $\blacksquare$

Steff9 wrote: As previously stated: test20 wrote: If every row and every column has value $k$, then the sum of all values (over all rows and all columns) is $S=2nk$. On the other hand, every domino contributes exactly $3$ to the total sum $S$; hence if there are $d$ dominoes then $S=3d$. This yields $S=2nk=3d$. (1) If $n$ is a multiple of $3$, then $d=2nk/3\ge 2n/3$. (2) If $n$ is not a multiple of $3$, then $d=2nk/3\ge 2n$. We proceed by showing that this minimum can be reached by constructing inductively for three separate cases as shown in the images below. For the cases where $n$ is not divisible by $3$, we always add two dominoes in the bottom-right $3\times 3$ square, and "move" (erase and duplicate) the dominoes from the top-right and bottom-left $3\times 3$ square from the previous step. (red domino: erased from previous step; green domino: added in this step)

I think your construction for $n=10$ is wrong, clearly the value of some rows is 4 and some others 3

The answer is $\frac{2n}3$ dominoes if $3 \mid n$, and $2n$ dominoes otherwise. First, we prove that this is the minimum. Suppose that there are $i$ dominoes on the board; then, double counting pairs $(r, d)$ where $r$ is a row or column and $d$ covers some square in $r$, we have $$2nk = 3i \implies i = \frac{2nk}3.$$For this to be a positive integer, we clearly have the above constraints on $k$ and thus constraints on $i$. To show that this is constructible, first check that $n=3$ through $n=7$ are constructible. Then, we proceed with induction. If $3 \mid n$, consider the top-left $3a \times 3a$ grid and bottom-right $3a \times 3b$ grid of the $n \times n$ grid, where $a+b=\frac n3$. By constructing valid tilings with $\frac{2a}3$ dominoes in the top-left and $\frac{2b}3$ dominoes in the top right, we can guarantee a consistent $k$-value in the $n \times n$ grid. Furthermore, such $a, b$ always exist due to our base cases. If $3 \nmid n$, we can do something similar, where we divide into an $a \times a$ and a $b \times b$ grid where $3 \nmid a$ and $3 \nmid b$ and $a+b=n$. For similar reasons, this yields a valid tiling, so we are done.

this one definitely deserves a post The answer is $d=\tfrac{2n}{3}$ for $3 \mid n$ and $d=2n$ otherwise, where $d$ is the number of dominoes. We first prove these are lower bounds. Each balanced configuration has value $k$ on each of its $n$ rows, and similarly its columns, so this gives a total sum of $2nk$ dominoes. But each domino is counted three times (once for the row or column it is entirely contained in, and once for each of the row or columns only one of its cells are contained in). Thus, for a balanced construction with value $k,$ there are $d=\tfrac{2nk}{3}$ dominoes. When $3 \mid n,$ the smallest $k$ such that $d$ is an integer is $k=1,$ giving a lower bound of $d=\tfrac{2n}{3}$ in this case. If $3 \nmid n,$ the smallest $k$ such that $d$ is an integer is $k=3,$ giving a lower bound of $d = 2n$ in this case. We now prove these are upper bounds. First consider $3 \mid n.$ Observe the below obvious configuration for $n=3:$ [asy][asy] import olympiad; unitsize(20); real d = 0.1; path r(int a, int b, int x, int y) { return (a-1+d,b-1+d)--(x-d,b-1+d)--(x-d,y-d)--(a-1+d,y-d)--cycle; } for (int i = 0; i <= 3; ++i) { draw((0,i)--(3,i)); draw((i,0)--(i,3)); } fill(r(1,2,1,3)); fill(r(2,1,3,1)); [/asy][/asy] Proceed by induction. Assume $n=3m$ has a valid configuration of $k=1$ using $\tfrac{2m}{3}$ dominoes. Extend the $3m \times 3m$ board into a $3m+3 \times 3m+3$ board by constructing $3$ columns to the left of the leftmost column, and $3$ rows below the bottommost row. Tile the remaining $3 \times 3$ square with the above construction for $n=3.$ This gives a working construction using $\tfrac{2m+6}{3}$ dominoes for $n=3m+3,$ completing the induction. Now consider when $3 \nmid n.$ Observe the below configurations for $n=4,5,$ and $7.$ [asy][asy] import olympiad; unitsize(18); real d = 0.1; path r(int a, int b, int x, int y) { return (a-1+d,b-1+d)--(x-d,b-1+d)--(x-d,y-d)--(a-1+d,y-d)--cycle; } for (int i = 0; i <= 4; ++i) { draw((0,i)--(4,i)); draw((i,0)--(i,4)); } fill(r(1,4,2,4)); fill(r(1,3,2,3)); fill(r(1,1,1,2)); fill(r(2,1,2,2)); fill(r(3,3,3,4)); fill(r(4,3,4,4)); fill(r(3,2,4,2)); fill(r(3,1,4,1)); [/asy][/asy] [asy][asy] import olympiad; unitsize(18); real d = 0.1; path r(int a, int b, int x, int y) { return (a-1+d,b-1+d)--(x-d,b-1+d)--(x-d,y-d)--(a-1+d,y-d)--cycle; } for (int i = 0; i <= 5; ++i) { draw((0,i)--(5,i)); draw((i,0)--(i,5)); } fill(r(1,1,1,2)); fill(r(1,3,2,3)); fill(r(3,2,3,3)); fill(r(2,1,3,1)); fill(r(1,4,1,5)); fill(r(2,4,2,5)); fill(r(3,4,3,5)); fill(r(4,1,5,1)); fill(r(4,2,5,2)); fill(r(4,3,5,3)); [/asy][/asy] [asy][asy] import olympiad; unitsize(18); real d = 0.1; path r(int a, int b, int x, int y) { return (a-1+d,b-1+d)--(x-d,b-1+d)--(x-d,y-d)--(a-1+d,y-d)--cycle; } for (int i = 0; i <= 7; ++i) { draw((0,i)--(7,i)); draw((i,0)--(i,7)); } fill(r(1,1,2,1)); fill(r(1,2,1,3)); fill(r(1,4,1,5)); fill(r(3,1,4,1)); fill(r(5,1,5,2)); fill(r(5,3,5,4)); fill(r(4,5,5,5)); fill(r(2,5,3,5)); fill(r(2,6,2,7)); fill(r(3,6,3,7)); fill(r(4,6,4,7)); fill(r(6,2,7,2)); fill(r(6,3,7,3)); fill(r(6,4,7,4)); [/asy][/asy] In each of these configurations, $k=3,$ and $d=2n.$ Observe that given two constructions of $k_1$ and $k_2,$ with $d=2k_1$ and $d=2k_2$ respectively, appending them in a diagonal block fashion creates a valid construction for $k_1+k_2$ with $d=2k_1+2k_2.$ By the Chicken McNugget theorem, the largest number that cannot be expressed as a linear combination of $4$ and $5$ is $4(5)-4-5=11.$ It remains to check valid configurations with $d=2n$ exist for $n=8,9,10,11.$ But observe $8=4+4, 9=4+5, 10=5+5,11=4+7,$ completing the proof.

The answer is $\frac{2n}{3}$ for $3\mid n$ and $2n$ for $3\nmid n$, so let's prove it. First, we notice that there are two ways of counting the total value of the board. Each of the $2n$ rows and columns have $k$ value each, so the total value is $2nk$. Also, each domino adds $3$ to the total value of the board, giving $3d$ total value, where $d$ is the number of dominoes. So, we have $2nk=3d$, meaning the minimum value of $d$ is $\frac{2n}{3}$ with $k=1$ for $3\mid n$ and $2n$ for $3\nmid n$ with $k=3$. We now prove that there is a construction for each $n\geq 3$ that satisfies that. First, we look at the $3\mid n$ case. For a $3\times 3$ grid, we have this construction. When $n=3x$ for some positive integer $x$, we can put $x$ of those $3\times 3$ grids along the diagonal of the $3x\times 3x$ grid such that no two cells of distinct $3\times 3$ grids are a part of the same row or column. Now, when $3\nmid n$, we see that we can find constructions for $n=4,5,7$. For $n>11$, by the Chicken McNugget Theorem, we can always find some $a,b\in\mathbb{Z}^+$ such that $4a+5b=n$, so we can place $a$ of our $n=4$ constructions, and $b$ of our $n=5$ constructions along the diagonal so that no two cells of distinct $4\times 4$ or $5\times 5$ grids are a part of the same row or column. Now we take care of the cases where $n\leq 11$ and $3\nmid n$. If $n=11$, we use an $n=4$ grid and an $n=7$ grid along the diagonal, because $11=4+7$. Similarly, we have $10=5+5$ and $8=4+4$. Since we have taken care of all cases, we're done.

Double-counting the total sum of the value of each row and column, we get the equation \[(2n) \cdot k = 3 \cdot d \implies k = \frac{3d}{2n}.\] We claim the optimal configuration is simply the least possible positive integer solution to this, or \[\boxed{\begin{cases} k=1, \quad d=\frac{2n}{3} & \text{ if } 3 \mid n \\ k=3, \quad d=2n & \text{ if } 3 \nmid n \end{cases}}\] Use induction. We can easily bash out the base cases $n=3,4,5,7$. We finish by using the following algorithm by assigning configurations to squares $A$ and $B$ while leaving the rest of the board blank. $n \equiv 0 \pmod 3$: $A=3$, $B=n-3$ $n \equiv 1 \pmod 3$: $A=5$, $B=n-5$ $n \equiv 2 \pmod 3$: $A=4$, $B=n-4$ Our inductive hypothesis tells us these smaller squares have share the same $k$ value, and thus our new construction also has this value. $\blacksquare$ [asy][asy] size(100); draw((0,0)--(1,0)--(1,1)--(0,1)--cycle); draw((.3,0)--(.3,1)^^(0,.7)--(1,.7)); label("$A$", (.15,.85), 0*dir(0)); label("$B$", (.65,.35), 0*dir(0)); [/asy][/asy]

Let d be the number of dominoes. Now 2.n.k = 3d, since we double-count the total sum of the value of each row and column $\Rightarrow$ $d = \frac{2nk}{3}$. We want d to be minimal $\Rightarrow$ we want k to be minimal. Now since d is an integer, we know $3 \mid 2nk$. Case 1: $3 \mid n$ d will be minimal if k = 1. For n = 3, we get an easy example for k = 1. Now for every $n = 3n_1$, we can divide the table into 3x3 squares and we should use the example for 3x3 table and copy it into the diagonal cells of the bigger table. $\Rightarrow$ for $3 \mid n$, we always have a working configuration and $d_{min}$ = $\frac{2n}{3}$. Case 2: $3 \nmid n$ Now if $3 \nmid n$, then since $3 \mid 2nk$, it follows that $3 \mid k$ $\Rightarrow$ $k \geq 3$. d will be minimal if k = 3, then d = 2n. We will prove that for every such n, we have a working configuration. For n = 4 and n = 5, we can find an easy example. Doing the diagonal trick for table with side $n_1 + n_2$, dividing it into smaller tables with $d = 2n_1$ and $d = 2n_2$, we get new $n_1 + n_2$ that works. We know that n = 4 and n = 5 work $\Rightarrow$ n = 8, 9, 10 work. If we find that n = 7 work, we basically find out that every n works, since we have 4 consecutive integers that work and we can just add 4 to each of them and get more new working integers, since n = 4 works. We can easily find a working example for n = 7 $\Rightarrow$ for every n, where $3 \nmid n$, $d_{min} = 2n.$ In conclusion for every n, there exists a working configuration. For n, such that $3 \mid n$, $d_{min} = \frac{2n}{3}$. For n, $3 \nmid n$, $d_{min} = 2n.$