Amoeba evacuation puzzle

[Rainman]

An amoeba is sitting on the bottom left square (A1) of a chessboard which extends infinitely upwards and to the right. You can make an amoeba split into two. If an amoeba is split into two, its offspring will take the square directly above and the square directly to the right of the parent amoeba. This vacates the square of the parent amoeba. So your first move, splitting the amoeba on A1, will put one amoeba on A2 and one amoeba on B1. An amoeba can only split if both spaces for its offspring are unoccupied. Your objective is for all the amoebas to evacuate the area A1, A2, A3, B1, B2, B3, C1, and C2. (Squares marked with x in drawing below)

...........

oooooooo...

oooooooo...

xxoooooo...

xxxooooo...

xxxooooo...

[Anza Power]

Good and quick solve, it's not possible to evacuate the area.

Yeah I think that is correct, here's why:

Divide the board into diagonal lines like so:

Now let's define c{i} to be the number of amoebas at diagonal i, let's give weights to the diagonals w{i}=0.5^i-1, so the weight of the first diagonal is 1 and the weight of every diagonal after that is half the weight of diagonal before it...

Now define board_sum to be the sum of the number of amoebas on each diagonal times the weight of that diagonal, boardsum_ = sum(c{i}w{i})...

At the beginning we have board_sum=1, whenever we make a move we split an amoaba at diagonal i into two amoebas at diagonal i+1, since the weight of diagonal i+1 is half that of diagonal i we can see that the board_sum has not changed...

So the board_sum is always constantly 1.

Now imagine the case where there is an infinite number of amoebas one in every cell, the board_sum in that case is:

(the convergence was calculated using the formula for the mean of a geometric distribution with parameter 0.5)

Now take away the amoebas at the cells we want to clear, their weight is:

1 + 0.5 + 0.5 + 0.25 + 0.25 + 0.25 + 0.125 + 0.125 = 3.

So the board_sum of the board when there is an infinite number of amoebas filling every cell except the ones that we need to clear is 1, which means that if the number of amoebas was finite then the board_sum would be less than 1 which is impossible...

Edited December 7, 2012 by Anza Power

[EventHorizon]

The first thing this reminded me of was the tower of hanoi puzzle. Simple moves, but a huge number of them.

There is a finite number of moves that will solve this, and even though the sequence of moves may differ the end configuration of all optimal (min moves) solutions will be the same.

There will only ever be 3 amoebae in the first column and only 3 in the first row.

The puzzle can be changed as follows and keep ending configurations and number of required moves the same (just the sequence of moves is altered):

Allow multiple amoebae in each square.

Allow any amoeba to split and add 1 amoeba to the right and above.

End configuration cannot have more than 1 amoeba in each square.

One amoeba and need to vacate it's spot.

1

1

01

Now if we continue and say vacate those spots...

1

01

01

1

02

001

11

011

001

Three amoebae.

1

11

+1 move

2

02

+4 moves

2

04

002

+3+2

1

14

014

0011

+6

13

116

0113

0011

+5+4

02

117

1117

01112

00110

+12+2

0,1

0,1,7,

1,1,1,12

1,1,1,1,7

0,1,1,1,1,1

0,0,1,1,0,0

Example 2 is not looking good. Perhaps it is unsolvable....

Proof no solution exists (for example 2 and therefore for the original problem)

From example 2, after 10 moves we get:

1

14

014

0011

This can be seen as

1

11

011

0011

added to (with shifted position... which doesn't affect number of moves)

3

03

which still needs to vacate their spots.

Assume it takes a finite number of moves, N, to accomplish the needed evacuation and 'flattening' for that second piece. Lets see what happens when we try...

+6 moves

3

06

003

+4+5 moves

2

17

017

0012

This configuration can be thought of as

2

14

014

0012

added to a shifted

3

03

Since the second piece is the original configuration we were trying to flatten, the number of needed moves must be 15 moves + N moves + more to flatten from here. But since we said it was only going to take the N moves and N < 15+N+ another positive number, N cannot be finite.

So it is not possible to evacuate and 'flatten' from the

3

03

configuration.

[phil1882]

start

1

first move

1

0 1

second move

1 1

0 0 1

third move

1 1

0 1 1

0 0 1

fourth move

1 1 1

0 1 1 1

0 0 0 1

fifth move

1 1 1

0 0 0 1

0 1 1 1

0 0 0 1

sixth move

1 1 1 1

0 1 1 0 1

0 0 1 1 1

0 0 0 0 1

seventh move

1 1 1 1 1

0 1 1 1 0 1

0 0 1 0 1 1

0 0 0 0 0 1

eighth move

1 1 1 1 1

0 1 1 1 0 1

0 0 1 0 0 1

0 0 0 0 1 1

0 0 0 0 0 1

i dont think its possible to do it in fewer.

[EventHorizon]

Looks like I misunderstood the initial configuration.

I assumed the x's were already amoeba and not just space to vacate.

Still not solvable...

1

1

01

1

02

001

1

03

003

0001

Still need to vacate

3

03

Which I showed was not possible

[EventHorizon]

...

fourth move

1 1 1

0 1 1 1

0 0 0 1

fifth move

1 1 1

0 0 0 1

0 1 1 1

0 0 0 1

...

From step 4 to step 5 the bottom two rows are identical, so you are saying you go from

111

to

111

0001

which should be

111

0111

Handy rule of thumb: Since each move (your moves are actually series of moves) adds one amoeba, check the number of amobae that split and make sure that the total number of amoebae before and after differ by this number.

[EventHorizon]

1

1

01 can vacate bottom left square

1

01

01

11

001

01

11

011

001 can vacate immediate neighbors of bottom left square

01

101

011

001

011

1001

011

001

011

1011

0101

001

011

1111

0011

001 can vacate 2x2 area

It may be easier with my other formulation of the problem.

I'll try and vacate

0

00

00

1

1

01

1

02

001

12

002

001

1

03

002

001 notice the 2 and the 3...

12

013

0011

001 notice that the 2 and the 3 swapped relative positions...

01

113

0112

0011

001 the 2 and the 3 swapped again. They'll continue to swap, and will never finish.

So it isn't possible to vacate that area.

So the best you can do is

00

00

or

0

0

...

0

0

000...00

1

1

01

1

01

01

11

001

01

11

011

001

01

101

011

001

11

011

011

001

111

0101

011

001

111

0111

0101

001

111

0111

0111

0001

001

1101

0111

0111

0001

011

1011

0111

0111

0001

111

0111

0111

0111

0001

1111

01101

0111

0111

0001

1111

01111

01101

0111

0001

1111

01111

01111

01101

0001

1111

01111

01111

01111

00001

etc.

[Rainman]

Good and quick solve, it's not possible to evacuate the area.

[Anza Power]

Interesting puzzle, I have implemented it in HTML/Javascript:

http://anzapower.web...moeba/game.html

It's not as easy as I expected...

[Rainman]

Yeah I think that is correct, here's why:

Divide the board into diagonal lines like so:

Now let's define c{i} to be the number of amoebas at diagonal i, let's give weights to the diagonals w{i}=0.5^i-1, so the weight of the first diagonal is 1 and the weight of every diagonal after that is half the weight of diagonal before it...

Now define board_sum to be the sum of the number of amoebas on each diagonal times the weight of that diagonal, boardsum_ = sum(c{i}w{i})...

At the beginning we have board_sum=1, whenever we make a move we split an amoaba at diagonal i into two amoebas at diagonal i+1, since the weight of diagonal i+1 is half that of diagonal i we can see that the board_sum has not changed...

So the board_sum is always constantly 1.

Now imagine the case where there is an infinite number of amoebas one in every cell, the board_sum in that case is:

(the convergence was calculated using the formula for the mean of a geometric distribution with parameter 0.5)

Now take away the amoebas at the cells we want to clear, their weight is:

1 + 0.5 + 0.5 + 0.25 + 0.25 + 0.25 + 0.125 + 0.125 = 3.

So the board_sum of the board when there is an infinite number of amoebas filling every cell except the ones that we need to clear is 1, which means that if the number of amoebas was finite then the board_sum would be less than 1 which is impossible...

That's the solution I had in mind for the problem, well done. I also enjoyed your javascript implementation of the problem.