Though not everyone proved minimality — and there were a couple of outright incorrect solutions — many of you solved this nice puzzle. Here is Zielinski's solution, assuming the corners are black.
First, shoot all the white squares (840), then all the black squares (841), then all the white squares again (840). This uses 2521 shots. To show this is best, cover the board with 840 dominoes, leaving one square uncovered. Imagine the tank to be restricted to never leave the domino it is on. Each domino is now independently analysable and requires at least 3 shots. The single uncovered square requires at least 1 shot. So the lower bound is 3 * 840 + 1 = 2521.
Robert Israel and Piotr Zielinski extended the problem to arbitrary graphs. Zielinski's notes follow.
To generalize, consider any undirected graph G. The tank sits at some vertex, and when that vertex is shot, it moves to an adjacent vertex. The goal is to hit the tank twice. The possibility of the tank not moving after being shot can be included here by adding an edge from a vertex to itself.
Let K be an independent set of vertices (no edges between vertices in K). Consider the following sequence of shots:
- Shoot all vertices not in K.
- Shoot all vertices in K.
- Shoot all vertices not in K again.
This sequence works because if the tank is originally not in K (so is hit in phase #1), it will then be hit again in either phase #2 or #3. If the task is initially in K, then after being hit in phase #2, it will move to not K (because there are no edges between vertices in K), and will be hit again in phase #3.
This process requires 2n − |K| shots, where n is the number of vertices. If K is the largest independent set, this is optimal, as shown below.
Consider any sequence S of shots that works, and let A be the set of vertices that are hit exactly once. Since every vertex needs to be hit at least once, this process requires requires at least 2n − |A| shots. What remains to be shown is that A is independent. If that's the case, then |A| ≤ |K|, so 2n − |A| ≥ 2n − |K|.
To show that A is independent, consider vertices x and y, both in A and connected by an edge. Without loss of generality, assume that x occurs before y in the shot sequence S. Consider the case in which the tank is originally at y, and after being hit, it moves to x. Since x was shot at before y, the tank will never be shot at again. This contradiction shows that there are no edges between nodes in A. That is, A is independent, as required. This concludes the proof.
Piotr then considers the generalization where we require the tank to be struck k times rather than 2. No definitive results were obtained.