Best way to fill a $8\times 8$ board You have an $8\times 8$ Battleships board and need to place battleships of sizes $1\times 1$, $1\times 2$, $1\times 3$, $1\times 4$, $1\times 5$ on the board to cover as much of the board as possible. The ships cannot touch another ship, even at the corners.
You can place as many of any size as you wish, what is the maximum number of squares you can fill? I believe the answer to this is 30, although not sure how you prove it is the highest.
Also how would you go about solving this for an $n\times n$ board. This probably relates to how you prove the answer for the first part.

32 is the best you can get. You can replace every $k\times 1$ ship by a $(k+1)\times 2$ rectangle on a $9\times 9$ board, and the ships are legally positioned iff the rectangles don't overlap. If $n$ ships cover $m$ squares, then the rectangles cover $2(m+n)$ squares, so $m+n\le 40$. Hence, if there are at least 8 ships, they cannot cover more than 32 squares. OTOH, 6 ships cover at most 30 squares. If there are 7 ships and at most 4 of them are of size 5, then they cover at most 32 squares. So, consider 5 ships of size 5 placed on the board. At least 3 of them are parallel to each other. We may assume they are horizontal. Each of them is closer to one vertical edge of the board than the other. We may assume two of them are closer to the left edge. Then there cannot be a vertical 5-square ship in any of the 6 leftmost columns, so there are 4 horizontal ships and 1 vertical one. But then there is room for one other ship only.
I haven't checked carefully the details I left out, but I hope the above is an essentially correct sketch.
