Skip to main content
1 of 2
Jukka Kohonen
  • 4.2k
  • 2
  • 21
  • 49

Assuming that "at most common entry" means that any two tuples $(x_1,\ldots,x_k)$ and $(y_1,\ldots,y_k)$ match in at most one position $i$, that is, there is a position $i$ such that $x_j \ne y_j$ for all $j \ne i$.

The claim is false for $n=2$ and any $k \ge 4$. We would need $n^2=4$ tuples $x,y,z,w$. Then each of $y$ and $z$ must differ from $x$ in at least $k-1$ coordinates, which implies that $y$ and $z$ match in at least $k-2 \ge 2$ coordinates.


(If the meaning was that any two tuples contain at most one common value, regardless of position, the claim would fail already with $n=2$, $k=2$, because there are only four different tuples $(1,1),(1,2),(2,1),(2,2)$, and $(1,2),(2,1)$ have two common values $1$ and $2$.)

Jukka Kohonen
  • 4.2k
  • 2
  • 21
  • 49