Find the number of neighbors in a Grid

Question

Chocolates are placed in a $100*60$ grid. You can place only one chocolate in every square of the grid. If two chocolates are in the same row or column, and there is no other chocolate between them, then they are called neighbor. Find the maximum number of chocolates that can be placed in the grid such that no chocolate does have more than two neighbors.

I have found filling a small $2*2$ grid fully with chocolates and keeping vacant just the next small $2*2$ grid gives the highest number of neighbors. But not sure with the approach.

Answer 1

We can solve this problem with an integer linear program. For a grid of length $n$ and height $m$:

\begin{align*} \max & \sum_{i,j} x_{ij} \\\\ & L_{ij} + R_{ij} + U_{ij} + D_{ij} \leq 4-2x_{ij} & \forall i,j \\\\ & L_{ij} \geq \frac{1}{n} \sum_{j<j'} x_{ij'} & \forall i,j \\\\ & R_{ij} \geq \frac{1}{n} \sum_{j'<j} x_{ij'} & \forall i,j \\\\ & U_{ij} \geq \frac{1}{m} \sum_{i<i'} x_{i'j} & \forall i,j \\\\ & D_{ij} \geq \frac{1}{m} \sum_{i'<i} x_{i'j} & \forall i,j \\\\ & L_{ij}, R_{ij}, U_{ij}, D_{ij}, x_{ij} \in \{0,1\} & \forall i,j. \end{align*}

Here $x_{ij} = 1$ iff there is a chocolate placed at $(i,j)$.

Intuitively, $L_{ij}=1$ if there is a chocolate on the left of $(i,j)$. Analogous with $R_{ij}, U_{ij}, D_{ij}$. More rigorously, $L_{ij}=0$ only if there is no chocolate on the left of $(i,j)$. $L_{ij}=1$ indicates that there may be a chocolate on the left of $(i,j)$.

Answer 2

I can get $160$ from the top and left edges plus the lower right corner. We can see by inspection that the pattern is acceptable as no chocolate has more than two neighbors by the problem definition. We can also see that no chocolates can be added without having one with at least three neighbors. I don't have a proof that another pattern will not be better.

Answer 3

The maximum number of chocolates is $160$. Ross Millikan found an optimal configuration, so I will just prove you can do no better.

Let $C$ be the set of chocolates, and let $L$ be the set of rows and columns of the grid. I will build an injective function $f:C\to L$, which proves that $|C|\le |L|=160$.

Consider the graph whose vertices are the chocolates, and two chocolates are joined by an edge if they share a row or column with no chocolates in between. Since every chocolate has at most two neighbors, each connected component of this graph is either a path or a cycle. Therefore, each component has a Hamiltonian path. Suppose a particular component has $m$ vertices, and let $v_1,v_2,\dots,v_m$ be a Hamiltonian path for that component. For each $i\in \{1,\dots,m\}$, we determine $f(v_i)$ as follows.

• If $i<m$, and $v_i$ and $v_{i+1}$ share a row, then $f(v_i)$ is the column containing $v_i$.

• If $i<m$, and $v_i$ and $v_{i+1}$ share a column, then $f(v_i)$ is the row containing $v_i$.

• When $i=m\dots$

  • If the connected component is a cycle, then determine $f(v_m)$ using the rules above, where $v_{i+1}$ refers to $v_1$.

  • If the component is a path, then $f(v_m)$ is the row containing $v_m$.

You can then prove that $f$ is injective.