Finding a Battleship of Uncertain Shape

Abstract

Motivated by a game of Battleship, we consider the problem of efficiently hitting a ship of an uncertain shape within a large playing board. Formally, we fix a dimension $d\in \{1,2\}$. A ship is a subset of ${\mathbb{Z}}^d$. Given a family $F$ of ships, we say that an infinite subset $X\subset {\mathbb{Z}}^d$ of the cells pierces $F$, if it intersects each translate of each ship in $F$ (by a vector in ${\mathbb{Z}}^d$). In this work, we study the lowest possible (asymptotic) density $\pi (F)$ of such a piercing subset. To our knowledge, this problem has previously been studied only in the special case $|F|=1$ (a single ship). As our main contribution, we present a formula for $\pi (F)$ when $F$ consists of 2 ships of size 2 each, and we identify the toughest families in several other cases. We also implement an algorithm for finding $\pi (F)$ in 1D.

10 pages, 6 figures