3

Given a rectangular grid with $n$ rows and $m$ columns in which squares may be placed, what are minimum number of squares required so that the next square added cannot be placed in isolation?

Isolation is defined as not attached to a side of at least 1 another square. A square only attached to the corner of another square is still isolated.

Example:

enter image description here

I have developed a spreadsheet to try and solve this but it does so in a sum-what convoluted way. I also keep finding problems with it. It needs adapting to work with all small grids (eg 1 by x shapes where x is 5 or greater, 2x5 and 3x6). You may or may not find it useful. link to spreadsheet

user247298
  • 133
  • 1
    Do squares with touching corners count as being in isolation of one another? – Myridium Feb 09 '16 at 22:33
  • Yes they are still isolated. I have developed a spreadsheet but it comes to an answer in a sum-what convoluted way. However I keep finding problems with it. It needs adapting to work with all small grids (eg 1 by x shapes where x is 5 or greater, 2x5 and 3x6). You may or may not find it useful. link – user247298 Feb 09 '16 at 22:36
  • 1
    I suggest editing your question to clarify my question about touching corners. That way, potential answerers to this question won't have to read the comments to find the full details (and are thus more likely to answer). Additionally, adding those example images on the excel sheet you linked me to the body of your question will make it more attractive and easier to digest. This will increase the chance that your question is answered in a satisfying way. – Myridium Feb 09 '16 at 22:45
  • Thanks @Myridium, I have made the changes you suggested. – user247298 Feb 09 '16 at 23:13
  • Thanks for taking it on board. Your question is now well-posed and gets my upvote. – Myridium Feb 09 '16 at 23:36

1 Answers1

2

Since each square touches itself and up to four others, the number required cannot be less than $\frac{nm}{5}$ and this is in a handwaving sense a possible limit when $n$ and $m \to \infty$ .

The only problem is the the edges, as shown here, where the "existing squares" are red. The problem might go away on a particular torus.

enter image description here

Henry
  • 157,058
  • pressed enter too soon. – user247298 Feb 10 '16 at 09:24
  • Thanks for your thoughts. I agree that the problem is the edges and that on a torus you could get $nm/5$. To resolve this we need to work out how often the white and red squares can be merged. On grids where $n>4$ and $m>4$ we could just look at the corners. If the distance between the corner and the closest white square on the $n$ axis $+$ the distance between the corner and the closest square on the $m$ axis $<5$, assuming the corner is square is counted as $1$, then only one of the $1$ white squares needs to be used. – user247298 Feb 10 '16 at 09:51
  • When the total is $48$ only $1$ white squares needs to be used when the closest red square is also moved. This is the logic I put into the spreadsheet, however it doesn't work consistently on smaller grids. – user247298 Feb 10 '16 at 09:51