21
$\begingroup$

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.

Question 1: Help the amoeba escape the following "cross" prison.

q1

Question 2: Help the amoeba escape the following "twisted cross" prison.

q2

Question 3: What about the following "octagon" prison, which is the combination of the previous two?

q3

Note:

  • The solutions are obviously not unique, as one may continue splitting after escaping from the prison. Thus in principle, you should try to use as few splittings as possible.

  • Click the pictures for larger versions. Although the picture only shows an $11 \times 11$ part of the grid, the actual grid is infinitely large and the solution may extend to outside.

Improve this question
$\endgroup$
5
  • $\begingroup$ My reading is that filling the prison is not at all a goal. The aim is to have the amoebas do their thing in such a way that, even though you have more of them at every step, they all end up out of the prison. $\endgroup$
    – Gareth McCaughan ♦
    Commented Nov 29, 2020 at 12:04
  • 1
    $\begingroup$ @GarethMcCaughan do you think it is like the minimum number of moves to escape all amoebas from the prison (grey area)? otherwise it seems kinda straight forward solution to me since it is infinite board. $\endgroup$
    – Oray
    Commented Nov 29, 2020 at 12:20
  • $\begingroup$ The main question is simply: can you? It is more challenging than you think, and the fact that the board is infinite is not enough to prove that you can do it. There are puzzles of this general type that are provably impossible. $\endgroup$
    – Gareth McCaughan ♦
    Commented Nov 29, 2020 at 12:28
  • $\begingroup$ @Gareth Your understanding is correct. $\endgroup$
    – WhatsUp
    Commented Nov 29, 2020 at 13:15
  • 5
    $\begingroup$ For what it's worth: there's a non-decreasing invariant for this puzzle where, if we say the weight of a position is the sum of $2^{-d}$ over all amoebas, where $d$ is the distance of each amoeba from the original position, then the weight never decreases with a splitting, thus is always at least what it started as (i.e. $1$). The weight of an arrangement with every cell filled would be $9$. Unless I messed up my calculation, the weight of the white cells in question $3$ is $1.75$, so this doesn't rule out it being possible - but does rule out most larger prisons. $\endgroup$
    – Milo Brandt
    Commented Nov 29, 2020 at 18:41

2 Answers 2

Reset to default
9
$\begingroup$

Here is the first part solution (Question 1):

enter image description here

Here is the second part solution (Question 2):

enter image description here

Improve this answer
$\endgroup$
3
  • $\begingroup$ This is a correct solution to the first question. I count that there are $38$ amoebas in the final status (i.e. $37$ splittings used). $\endgroup$
    – WhatsUp
    Commented Nov 29, 2020 at 16:17
  • $\begingroup$ Thank you for the answer! Your solution to the second part is also correct, and there are $56$ amoebas in the final status (i.e. $55$ splittings used). Unfortunately I cannot upvote twice :P Since your solution is symmetric, you could actually just do half of it and hence save some work. $\endgroup$
    – WhatsUp
    Commented Nov 29, 2020 at 16:58
  • $\begingroup$ @WhatsUp :) that's fine, let's see if I can finish the last one. $\endgroup$
    – Oray
    Commented Nov 29, 2020 at 16:59
4
$\begingroup$

My solution for question 2

48 amoebas, pictures show the right half after splitting horizontally
enter image description here

Improve this answer
$\endgroup$
1
  • $\begingroup$ Nice solution and beautiful presentation! $\endgroup$
    – WhatsUp
    Commented Nov 29, 2020 at 23:58

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