Finding a Battleship of Uncertain Shape

MaRDI QIDQ6391414zbMATH OpenFDO

Authors Eva-Maria Hainzl, Maarten Löffler, Daniel Perz, Josef Tkadlec, Markus Wallinger

Publication date 17 February 2022

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 $din1,2$. A ship is a subset of $mathbb{Z}^d$. Given a family $F$ of ships, we say that an infinite subset $Xsubsetmathbb{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.

This page was built for publication: Finding a Battleship of Uncertain Shape

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6391414)