Maximum number of distinct elements in matrix of size $p \times p$, given for any row/column, there are $\le p-1$ distinct elements. Prove that for any given prime $p \ge 5$, there doesn't exist any matrix of size $p\times p : [x_{i,j} | i,j\in \mathbb{Z}, 0\le i,j \le p-1]$, such that

*

*$\forall i_0, \exists j_1, j_2 (x_{i_0,j_1} = x_{i_0,j_2})$, i.e., for any row $i_0$, there are $\le p-1$ distinct elements in it

*$\forall j_0, \exists i_1, i_2 (x_{i_1,j_0} = x_{i_2,j_0})$, i.e., for any column $j_0$, there are $\le p-1$ distinct elements in it

*$\exists\mathbb{S} \text{ s.t.} \left\vert \mathbb{S}=\{y \,\,| \,\,\exists i, j (y = x_{i,j})\} \right\vert > (p-1)^2$, i.e., there are $> (p-1)^2$ distinct elements in the matrix


This is to complete the proof in my answer here, I was able to prove the cases for large $n$ and some other cases, but some cases are still left to prove. The above problem seems to be the base case for all the other cases. I don't believe this counts as a duplicate, but if it does I can remove it.
I have used contradiction to show there cannot exist a set with $\ge (p-1)^2 + \frac{p-1}{2}$ distinct elements in that answer, but I have not used the fact that $p$ is prime anywhere; and checking for some small examples, it seems really important that $p$ is prime, but I cannot think on how to use this.
 A: Call a square matrix "qualifying" if no row or column has all distinct entries.

Fix an integer $n\ge 2$, and let $M$ be an $n{\times}n$ matrix such that the $(n-1)^2$ entries $M[i,j]$ entries with $1\le i,j\le n-1$ are all distinct, and also

*

*$M[i,n]=M[i,n-1]\;$for $1\le i\le n-1$.$\\[4pt]$

*$M[n,j]=M[n-1,j]\;$for $1\le j\le n-1$.$\\[4pt]$

*$M[n,n]=M[n-1,n-1]$, hence also $M[n.n]=M[n,n-1]$ and $M[n,n]=M[n-1,n]$.

Then $M$ is a qualifying $n{\times}n$ matrix with exactly $(n-1)^2$ distinct entries.

But for $n\ge 4$ we can do better . . .

Fix an integer $n\ge 4$, and let $M$ be an $n{\times}n$ matrix expressed in block form as
$$
M=
\begin{bmatrix}
A&C\\
D&B\\
\end{bmatrix}
$$
where

*

*$A$ is a $2{\times}2$ matrix with all equal entries.$\\[4pt]$

*$B$ is a qualifying $(n-2){\times}(n-2)$ matrix with exactly $(n-3)^2$ distinct entries.$\\[4pt]$

*$C$ is a $2{\times}(n-2)$ matrix with all distinct entries.$\\[4pt]$

*$D$ is an $(n-2){\times}2$ matrix with all distinct entries.

and such that none of $A,B,C,D$ has any entries in common with any of the others.

Since the matrices $A,B$ are qualifying, it follows that $M$ is qualifying.

Summing the number of distinct entries for $A,B,C,D$ we get
$$
1+(n-3)^2+2(n-2)+2(n-2)
=
n^2-2n+2
=
(n-1)^2+1
$$
hence $M$ is a qualifying $n{\times}n$ matrix with exactly $(n-1)^2+1$ distinct entries.

As an example, for $n=5$, the matrix
$$
M=
\begin{bmatrix}
0&0&1&2&3\\
0&0&4&5&6\\
7&8&13&!4&14\\
9&10&15&16&16\\
11&12&15&16&16\\
\end{bmatrix}
$$
is a qualifying $5{\times}5$ matrix with exactly$\,17=(5-1)^2+1\;$distinct entries.
