Bulgaria competition problems, 2022

Denote the table rows by $u_1, u_2, \dots, u_n$. Let $d(u_i, u_j)$, $i \ne j$ be the number of positions, in which the rows $u_i$ and $u_j$ differ. According to the statement $d(u_i, u_j) \ge m - k$. Then:
$$(1) \qquad S = \sum_{1 \le i < j \le n} d(u_i, u_j) \ge \frac{n(n-1)}{2}(m-k).$$

Consider an arbitrary table column and let it contain $x$ letters $a$, $y$ letters $b$, and $z$ letters $c$, with $x+y+z=n$. The contribution to $S$ of this column is exactly $xy+xz+yz$, and due to the inequality
$$n^2 = (x + y + z)^2 \ge 3(xy + xz + yz)$$
it follows that every column adds at most $\frac{n^2}{3}$ to the value of $S$ (this is the case iff $3$ divides $n$ and every column there are exactly $\frac{n}{3}$ letters of each type). Now (1) gives rise to:
$$(2) \qquad \frac{mn^2}{3} \ge S \ge \frac{n(n-1)}{2}(m-k) \iff mn + 3k \le 3kn + 3m.$$

Repeating the arguments, when replacing rows and columns leads to:
$$(3) \qquad mn + 3k \le 3km + 3n.$$
We add (2) and (3) to obtain $2mn+6k \le 3(m+n)(k+1) \Leftrightarrow \frac{2mn+6k}{3(m+n)} \le k+1$. Therefore, $\frac{2mn+6k}{3(m+n)} = k+1$, $mn+3k = 3kn+3m$, and $mn+3k = 3km+3n$ (meaning also that both $m$ and $n$ are divisible by $3$). From $3kn+3m = 3km+3n \Leftrightarrow (k-1)(n-m) = 0$, it follows that either $k=1$ or $m=n$. For $k=1$, $mn+3 = 3m+3n$, which is impossible, since $3$ divides $m$ and $n$, thus $9$ divides the RHS but not the LHS. For $m=n$, $m^2-3(k+1)m+3k=0$, with discriminant $D = 9k^2+18k+9-12k = (3k+1)^2+8$ a perfect square. From $(3k+1)^2+8 = t^2$ we deduce that the difference between two perfect squares is $8$, which holds

true only for $t=3$ and $k=0$. In conclusion $m=n=3$ and the table is: