Skip to main content
2 of 3
added 74 characters in body
Ilya Bogdanov
  • 23.7k
  • 54
  • 92

I assume that the interpretation with $\ell_\infty$-distance is correct.

If $n=k^2$, you may achieve $d=k$ but not more.

To achieve $d=k$, enumerate rows and columns from $1$ through $n$ and put ones in all cells of the form $(i, ik\mod (n+1))$, where $i=1,2,\dots,n$.

To see this is optimal, assume that $d=k+1$ is achieved. Consider ones in the first $d$ columns; they must be spread vertically at distances at least $d$ from each other, so we should have $n-1\geq d(d-1)$ which is wrong.

Ilya Bogdanov
  • 23.7k
  • 54
  • 92