6
$\begingroup$

As an extension to @WhatsUp 's question here, the rules of which are included below, with the following differences:

In one of the squares, there lives an amoeba (marked as a circle in the following pictures).

In some of the squares, there are amoebas (marked as green/yellow in the following picture).

On the grid, there is a region called "the prison" (painted grey in the following pictures).

Here "the prison" consists of all yellow and green squares.

plus-sign, 7 wide and 7 tall, bottommost square is yellow

  1. If the yellowish, bottommost square is unoccupied, can the amoebas make their escape? How hard is it?

  2. The night before their escape is launched, the yellow cell is filled with a new amoeba prisoner (all yellow and green are considered filled), what can they do now?

Reference

There is an infinite grid of squares.

In one of the squares, there lives an amoeba (marked as a circle in the following pictures).

Amoebas cannot move, but they can perform their unique action: an amoeba can split itself into two amoebas, which are identical to the original one, and each will occupy a square that is (orthogonally) adjacent to the original square.

Since every square can only accommodate one amoeba, a splitting can only happen when the amoeba has at least two empty adjacent squares (if there are more than two, then it can choose freely to which squares to split). Also, two amoebas should not split simultaneously, so that no conflict should occur.

On the grid, there is a region called "the prison" (painted grey in the following pictures). The aim is to let the amoebas escape the prison, i.e. to reach a status that no amoeba is in the prison.

$\endgroup$
1
  • 1
    $\begingroup$ Something that might help people understand why the problem is difficult - if you're trying to get all the amoebas away from the center, their numbers grow at an exponential rate but the number of squares they can occupy only grow at a polynomial rate. $\endgroup$ – Rob Watts Dec 2 '20 at 16:55
8
$\begingroup$

Answer to Q2. As @Milo Brandt points out in a comment to the referenced Q there is the following half invariant:

Put integer coordinates on the grid with (0,0) being the cross's center. Weight square (n,m) by $2^{-\lvert n \rvert - \lvert m \rvert}$. Then one can easily verify that

enter image description here 1. the weight of the entire (infinite) board is 9 (c.f. picture)
and
2. the weight of squares occupied by amoeba never goes down.

As the weight of the entire cross is $4\frac 1 2$ which equals the weight of its (infinite) complement the amoeba cannot escape in finitely many moves.

$\endgroup$
4
  • $\begingroup$ Rot13(Naq fvapr lbh pnaabg trg zber (guna 8/7) fdhnerf svyyrq ba z=0 be a=0 jvgubhg fhobcgvzny zbirf, vg vf abg cbffvoyr ng nyy) $\endgroup$ – Retudin Dec 1 '20 at 7:29
  • 1
    $\begingroup$ There is also a very pleasing graphical proof/representation of the total weight being 9, part of which was my motivation for this question. $\endgroup$ – Cireo Dec 1 '20 at 18:29
  • $\begingroup$ @Cireo like <see edit>? $\endgroup$ – Paul Panzer Dec 1 '20 at 21:38
  • $\begingroup$ @PaulPanzer if I could upvote twice ;) $\endgroup$ – Cireo Dec 1 '20 at 22:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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