16
$\begingroup$

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.

enter image description here

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

$\endgroup$
3
  • $\begingroup$ As a first observation, if we paint the board in a checker pattern, then the difference between the numbers of black and white blobs must be a multiple of five. I would expect this to be sufficient unless there are other easily observable necessary conditions. $\endgroup$
    – WhatsUp
    Feb 24, 2022 at 9:37
  • 2
    $\begingroup$ Do we only need to solve for the case of exterminating a finite number of blobs in a finite amount of time? $\endgroup$
    – noedne
    Feb 24, 2022 at 9:46
  • 2
    $\begingroup$ @noedne Finite only! If you allow infinite move sequences in the same vein as defining infinite moves in Conway's soldiers), then it is possible to exterminate a plane containing a single blob (puzzle: how?). Therefore, you can eliminate any finite set of blobs, destroying the cool invariant. $\endgroup$ Feb 24, 2022 at 15:51

1 Answer 1

19
$\begingroup$

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

blob on b2. circles on c1, c3, d2. arrow from b2 to d2
If the circled squares are empty, we can move this blob 2 spaces to the right like this:

blob on b2blobs on a2, b1, b3, c2blobs on a2, b1, b2, b3, c1, c3, d2blob on d2

Isolated diagonal movement

blob on c2. circles on a2, b1, b3, c2, d1, d3, e2. arrow from c2 to d3 If the circled squares are empty, we can move this blob diagonally 1 space up and right like this:

blob on c2blobs on b2, c1, c3, d2blobs on b2, c1, c2, c3, d1, d3, e2blobs on b2, d3, e2blobs on a2, b1, b3, c2, d3, e2blobs on a2, b1, b2, b3, c1, c3, d2, d3, e2blob on d3

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

blobs on a1, b2, c1, c3, d2
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:

blobs on a1, b2, c1, c3, d2blobs on a1, a2, b1, b3, c1, c2, c3, d2no blobs

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.