slides
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 ∈ {1, 2}. A ship is a subset of $\mathbb Z^d$. Given a family $\mathcal F$ of ships, we say that an infinite subset $P\subset\mathbb Z^d$ of the cells pierces $\mathcal F$, if it intersects each translate of each ship in $\mathcal F$ (by a vector in $\mathbb Z^d$). In this work, we study the lowest possible (asymptotic) density of such a piercing subset.