Is the following true? For every $n \geq 1, k\geq 2$, there is a set $S \subseteq [n]^k$ of size $|S| = n^2$ such that every two $k$-tuples in $S$ have at most one common entry.


Does anyone know if this is true? Is there a reference?



k-partite design
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*, that is, there is at most one $i$ such that $x\_i=y\_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$ positions, which implies that $y$ and $z$ match in at least $k-2 \ge 2$ positions.




---


(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$.)


