The solution is 2521 Explanation:
Suppose you checker the 41x41 field such that there are two colors, white and black, and no adjacent squares have the same color. Therefore 840 squares are black and 841 are white, or vice-versa. Suppose the tank is in a black square. If you hit all black squares, the tank will move to a white square, because there are no adjacent black squares. Therefore you can bomb all the white squares and the tank is killed. So, to definitely kill the tank, your run must include one bombing of all black squares followed by one bombing of all white squares. The situation is similar if you start with white. So, your run must include one bombing of all white squares followed by one bombing of all black squares. The shortest run that satisfies all these requirements is black-white-black, which requires 840+841+840=2521 bombs to be dropped.
I am not convinced that you've shown that it cannot be done in fewer moves. It seems that you are begging the question: why must you necessarily bomb all the black squares at once? In fact, it is not necessary: I can think of many other sequences that destroy the tank in 2521 moves.
aye, in fact I think it's possible to prove that it works with any configuration of black and white such that no two black squares touch. 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. Therefore the total number of bombings must equal nW*2 + nB to destroy the tank, where nW + nB = 1681 and no black squares touch. Thus the problem is finding a configuration of black and white such that no black squares touch and nW is as low as possible. The obvious answer is the checkerboard which makes nW = 840 and nB = 841. this doesn't actually require that all the white or black squares are bombed at the same time. So long as any possible sequence of tank motion(ie a square + all its neighbors) are bombed in this pattern it will work, it's just easier to determine the pattern beforehand and do them all at once instead of iteratively. For instance, bombing on successive diagonal stripes across the board(I hope this image gets across. Like starting in the top-left corner, then bombing its neighbors, then bombing the top-left corner again, then bombing another diagonal stripe) is actually the same as the checker board, just in a different order. I hope that made sense.
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.