The following combinatorial problem is a missing piece in a larger problem related to the smoothed analysis of algorithms, on which I am currently stuck.

Let $x$ be an $n \times n$ matrix with entries taking integer values in $\{1,2,..,p\}$. What is the smallest $n=n(p)$ that guarantees $x_{i,j}=x_{i,k}=x_{j+1,k}$ for some $i, j, k$ with $1 \le i \le j < k \le n$?

For $p=2$ I have checked that $n=n(2)=5$. For general $p$, I would like either an upper bound on $n(p)$ that is polynomial in $p$, or else an argument that the growth is superpolynomial.