In fact if the tank starts on a black square, you must merely bomb that ONE square before all of its neighbours. You say that it's necessary to bomb all the black squares first, use that claim as proof for a lower bound, then admit in the next paragraph that in fact bombing all the black squares first is unnecessary. So I still don't see how you've shown that it's impossible to destroy the tank in fewer shots. Perhaps by some clever interleaving of black and white squares you might save a missile or two?if the tank starts on a black square, you must bomb all black squares and then all white squares. If the tank starts in a white square, you must bomb all white squares and then all black squares and then all white squares. Therefore the bombing run must be W-B-W.
What I'm trying to say is that all black squares have to be bombed before their adjacent white squares, so bombing all blacks and then all whites is the same as bombing them in some other pattern that meets the same requirements and outputs the same number(for instance, bombing all whites in a row then bombing all blacks in a row). The checkerboard is the smallest that meets the requirements because it pairs every black with one adjacent white (plus the extra one), so if you added one more black it would require that two pairs of blacks exist. EDIT: in fact, I suppose you could use that pairing scheme to always bomb any configuration of squares in at most nSquares*3/2 + remainders
Sorry, but I still only have a very hazy idea of what you're trying to say! It seems like a very slippery argument and I'm not sure that it holds water. Could you make it more rigorous? The first claim is that each black square must be bombed before its adjacent white squares. I take this to mean that if S is a guaranteed-tank-destroying sequence of firing coordinates, and b is some particular black square with w some particular neighbor of b, then the first occurence of b in S must fall before the last occurence of w. (That is, b may be targeted after w as many times as one pleases, as long as w is targeted at least once after the first targeting of b.) The next statement is: "bombing all blacks and then all whites is the same as bombing them in some other pattern that meets the same requirements and outputs the same number(for instance, bombing all whites in a row then bombing all blacks in a row.)" And here I'm completely lost: What does it mean, precisely, for two firing sequences to be "the same"? Does it mean that either they both are guaranteed to kill the tank or they both are not, and that they are also of the same length?~
well, keep in mind the guaranteed tank-destroying sequence is actually white-black-white, I was simplifying just so I didn't have to type that much. And yes, you got that part exactly right. As for your question, I suppose for two sequences to be the same means that they both a)destroy the tanks and b)hit the same squares the same amount of times. Thus they'd have to follow the same W-B-W rules and could be morphed into each other so that a more computationally intensive process becomes static or vice-versa. Forgive me if this seems unimportant, I tend to think in terms of algorithms.