Tank Hunt - Futility Closet

A puzzle from Daniel J. Velleman and Stan Wagon’s excellent 2020 problem collection Bicycle or Unicycle?:

Before you is a field of 225 squares arranged in a 15×15 grid. One of the squares contains a perfectly camouflaged tank that you’re trying to destroy. You have a weapon that will destroy one square of the grid with each shot, but it takes two shots to destroy the tank, and you know that when the tank has been hit the first time (and only then) it will flee invisibly to an adjacent square (horizontally or vertically). What’s the minimum number of shots you’ll need to be sure of destroying it?

	Select Click for Answer
Imagine the field as a checkerboard with white corners. Shoot the 112 black squares, then the 113 white squares, then the black squares again. Two of these shots must hit the tank; in the worst case this will take 337 shots. To see that this is best, imagine covering the field with 112 dominoes, leaving one square uncovered, and suppose that the tank is restricted to its domino. We can study each domino independently: Each will require three shots, and the uncovered square requires a shot as well. So the lower bound is 3 × 112 + 1 = 337.

Click for Answer