Exterminating blobs on a grid

Question

On an infinite square grid, some of the squares are occupied by little creatures called blobs. Cute as they are, it is your mission to exterminate all of them! You only have two methods at your disposal for getting rid of blobs:

• If there are two blobs which are horizontally or vertically adjacent, you can provoke them to fight each other. This removes both blobs.

• If a blob is surrounded by four empty cells, you can poke the blob. This causes the blob to split into four new blobs, which will occupy the four neighboring cells. _{(This potential for rapid growth explains why they need to be exterminated).}

Otherwise, the blobs will not move.

Question: Given an arrangement of blobs, how can you determine whether it is possible to exterminate them all? What strategy can you use to succeed when possible?

If you are going to claim a blob arrangement is un-winnable, you had better provide an airtight proof, or else your boss will not let you off the hook.

Here are two example moves. In the first, we provoke two of the middle blobs to fight each other. This frees up space to poke the other central blob. Remember there is no end to the grid in this problem, despite how I drew these examples. In the first picture, it is legal to poke the upper-left blob.

This was problem #12309 submitted to the American Mathematical Monthly, I just added some flavor text.

Answer 1

Given an arrangement of blobs, how can you determine whether it is possible to exterminate them all?

First, let's color the grid in a checkerboard pattern. We'll call the groups of squares light squares and dark squares. Note the effect of each possible move on the count of blobs on each group:
• provoking: -1 light, -1 dark
• poking a light square: -1 light, +4 dark
• poking a dark square: +4 light, -1 dark
Observe that in each case, the difference between the number of blobs on light and dark squares changes by a multiple of 5 (0 or ±5). Therefore, given an arrangement of blobs, if the difference between the number of blobs on light and dark squares is not a multiple of 5, then extermination is impossible. All that remains is to show the converse: Extermination is possible if the difference is a multiple of 5.

What strategy can you use to succeed when possible?

Warning: what follows is a constructive but highly inefficient strategy. Do not try this at home.

Outline:

1. Exterminate blobs on light squares.
2. Show how to move a blob orthogonally.
3. Show how to move a solitary blob diagonally.
4. Show how to move a crowded blob diagonally.
5. Move blobs to where they can be exterminated in groups.

Light square blobs

While there exists some blob on a light square, exterminate it by either provoking it with a neighboring blob on a dark square or poking it if it has no neighbors. From now on, we'll assume that all blobs are on dark squares except during intermediate steps.

Orthogonal movement

If the circled squares are empty, we can move this blob 2 spaces to the right like this:

→ → →

Isolated diagonal movement

If the circled squares are empty, we can move this blob diagonally 1 space up and right like this:

→ → → → → →

Crowded diagonal movement

With extra work, we can move a blob diagonally even with blobs on the circled squares above as long as the destination square is free. Call the blob to move Bob.

1. First, let's give Bob some breathing room. If there are any blobs in columns to the right of Bob, then take the blobs in the column farthest to the right and move them 2 spaces farther right, one at a time. Repeat this with the second farthest column with blobs, if it exists, etc. Repeat all of this in each of the other 3 directions.
2. After clearing the dance floor, watch Bob perform the electric slide as before.
3. Finally, perform the same moves in step 1 in reverse order and direction to restore everyone other than Bob to their original squares.

Extermination

Pick an empty group of 5 dark squares far away from any blobs, in the pattern shown above. This will be the designated extermination zone. While there are at least 5 blobs, move the 5 closest to the zone to it, one at a time, using a sequence of diagonal moves. Then exterminate them like so:

→ →

Repeat until fewer than 5 blobs remain.

If the difference between the number of blobs on light and dark squares at the start was a multiple of 5, then it still is. Because there are no blobs on light squares and fewer than 5 blobs on dark squares, the number of blobs on dark squares must be 0. Extermination complete!