6

A coworker posed this problem as "The Battleship Problem":

A battleship starts at some unknown initial location $i\in\mathbb{Z}_n$ and moves at a constant velocity $v$ each turn. Each turn $t$ you may drop a bomb on one predetermined location, and the ship is destroyed if it occupies that position (that is, if $x_t=tv+i\pmod n$). What is the fewest number of turns required to guarantee that you destroy the ship?

Trivially it can be done by dropping $n$ bombs on each location, because after $n$ turns the ship is always back where it started. It turns out that it can actually be done in $2n-1$ (or less) turns for all $n<35$ (this was discovered by brute-force search). Is this true for all $n$?

I can show that it is true for primes as follows:

  • $x_t=0$ for $0\leq t<n$ (all $v\neq 0$ are generators of $\mathbb{Z}_n$).
  • $x_t=t$ for $n\leq t<2n$ (all locations for $v=0$).
  • The zero common to both parts can be eliminated for a total length of $2n-1$.

And similar logic shows that the same sequence works for prime powers.

I have not been able to come up with anything for odd composite numbers. What I'm hoping for is an algorithm to generate sequences given $n$, or keywords I can research to make progress on that.

user26857
  • 52,094
Dan Sanders
  • 61
  • That problem descriptions seems incomplete. Is the drop position the same as the ship position? What is the condition for the target ship to be destroyed? How large is the target ship? – mvw Oct 09 '15 at 21:52
  • I've updated the text to be more clear, but the answers are: the drop locations are a predetermined sequence, and the ship moves a fixed amount each turn. The ship is destroyed if its location is the same as a drop location on some turn. The target ship occupies one point. – Dan Sanders Oct 09 '15 at 22:00
  • This is a good problem. The ship is traveling on some coset of one of $\mathbb{Z}_n$'s sub-groups (trivial and improper subgroups included). If $m$ is the order of one of these cosets then I only see two ways to eliminate it: select one of it's elements $m$ consecutive times or select each element on turns separated by some factor of $m$ (i.e. for ${1,4}$ in $\mathbb{Z}_6$ I could select $\dots 4,x,1 \dots$ or $\dots 1,x,x,x,4 \dots$ etc). Doing this efficiently is tough. – Luke Oct 10 '15 at 00:10
  • I'm not sure if I've understood correctly: the ship is moving in one direction along an $n$-gon (with numbered vertices, etc.) at a constant speed, and each turn, you can drop a bomb at one of the vertices? In that case, why is the 'trivial' solution dropping $n$ bombs on each location, rather than just at one location? – shardulc Oct 10 '15 at 08:07
  • Notice that if it's sufficient to bomb $n$ times every location in the first half of the circuit and then to bomb once the remaining spots. This doesn't give $2n-1$ but at least lower the bound of the optimal solution. – mrprottolo Oct 10 '15 at 11:52
  • shardulc: When gcd(n, v) $\neq$ 1 the ship does not visit every location. mrmrottolo: In fact we can drop n/(x+1) at each x = 0, 1, 2... for overall O(n log n) drops. – Dan Sanders Oct 10 '15 at 20:32
  • I wish I had more time to fiddle with this problem, but I think the cases that you want to prove things for are indeed products of primes/ numbers for which the totient function is minimized, then I would try to prove that the best strategy is necessarily "piecewise linear". I also expect any strategy which is O(n) to fail, but expect counterexamples to be very large, due to the extremely slow convergence of $\phi(n)/n$ to zero. – ZKe Oct 15 '15 at 21:54

0 Answers0