9 replies to this topic

[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...

[EventHorizon]

Spoiler for Initial thoughts

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.

Spoiler for Example 1

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

Spoiler for Example 2

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....

Spoiler for Looks like I was wrong in my initial thoughts...

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]

Spoiler for

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.

Spoiler for but...

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]

Spoiler for

...
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
...

Spoiler for You can't get there from here...

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]

Spoiler for What area can you vacate?

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

Spoiler for More futility

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

Spoiler for second one

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...

[Anza Power]

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

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

Spoiler for

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 by Anza Power, 07 December 2012 - 06:54 PM.

[Rainman]

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

Spoiler for

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.