a thoughtful web.
Good ideas and conversation. No ads, no tracking.   Login or Take a Tour!
comment by dingus
dingus  ·  2545 days ago  ·  link  ·    ·  parent  ·  post: A puzzle: How to most quickly destroy the tank?

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.

yakov  ·  2545 days ago  ·  link  ·

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.

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?

dingus  ·  2545 days ago  ·  link  ·

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

yakov  ·  2545 days ago  ·  link  ·

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?~

dingus  ·  2545 days ago  ·  link  ·

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.