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?

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.