Skip to main content
added 85 characters in body
Source Link
Ilya Bogdanov
  • 23.7k
  • 54
  • 92

I assume that the interpretation with $\ell_\infty$-distance is correct, I.e., the distance between entries $(i,j)$ and $(i’,j’)$ is $\max\{|i-i’|,|j-j’|\}$.

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.

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.

I assume that the interpretation with $\ell_\infty$-distance is correct, I.e., the distance between entries $(i,j)$ and $(i’,j’)$ is $\max\{|i-i’|,|j-j’|\}$.

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.

added 74 characters in body
Source Link
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.

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.

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.

Source Link
Ilya Bogdanov
  • 23.7k
  • 54
  • 92

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.