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?
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityIs 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?
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$.)