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 $x$ be an n x $n \times n$ matrix with entries taking integer values in {1,2,..,p}. ${1,2,..,p}$. What is the smallest n=n(p) $n=n(p)$ that guarantees x[i,j]=x[i,k]=x[j+1,k] $x_{i,j}=x_{i,k}=x_{j+1,k}$ for some i,j,k $i, j, k$ with $1 <= \le i <= \le j < k <= n\le n$?
For p=2 $p=2$ I have checked that n=n(2)=5. $n=n(2)=5$. For general p, $p$, I would like either an upper bound on n(p) $n(p)$ that is polynomial in p, $p$, or else an argument that the growth is superpolynomial.
