This question is inspired by Oray's puzzle Lots of ships in the battleship.
You have an $n\times n$ grid (a battleship board) and a certain number of $2\times2$ squares (ships) to place in the grid. The rules are, quoting from Oray's post complete with illustrative gifs, as follows:
This time, you are going to put the ships one by one shown as the example below. Every time you put a ship, it cannot share more than 1 grid with other ships. That is, it must occupy at least three empty grids. In this case,
At most how many ships can you put into the board?
If this question was asked for $4$x$4$, the answer would be $5$ as shown below:
Here is the wrong way playing the game where you put the green ship, it shares two grid at the same time when you put it:
The method in ffao's answer establishes an upper bound of $1+\frac{n^2-4}{3}=\frac{n^2-1}{3}$, the theoretical maximum possible number of ships that could be placed on the board.
For which values of $n$ can this maximum be achieved?
E.g.:
- for $n=4$, the theoretical maximum of $5$ can be achieved as shown in the first gif above;
for $n=8$, the theoretical maximum of $21$ can be achieved as follows:
h h i i k k l l
h f f i k j j l
g f b b e e j m
g g b a a e m m
o o c a a d s s
o n c c d d r s
p n n q u r r t
p p q q u u t t
for $n=14$ (Oray's puzzle), the theoretical maximum of $65$ apparently cannot be achieved (although we haven't seen a proof of this yet).
Is there a general rule for which $n$ it can be achieved and which it can't?
No comments:
Post a Comment