Is the following true? For every n≥1,k≥2, there is a set S⊆[n]k of size |S|=n2 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?

**Answer**

Assuming that “at most common entry” means that any two tuples (x1,…,xk) and (y1,…,yk) *match in at most one position*, that is, there is at most one i such that xi=yi.

The claim is false for n=2 and any k≥4. We would need n2=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≥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.)

**Attribution***Source : Link , Question Author : Lior Gishboliner , Answer Author : Jukka Kohonen*