# Another infinite chessboard

Dejection
Posers and Puzzles 15 Jun '08 11:36
1. 15 Jun '08 11:36
This problem is very similar to the last one. Hopefully many of you will be able to solve it!

Suppose we have the bottom left hand corner of a chessboard, and this chessboard extends up and to the left forever. Call the bottom left corner (0,0), the one to the right of that (1,0) and the one above that one (1,1) etc. You get the gist. Think of the first quadrant of a cartesian plane, but only with integers.

Now we have three blobs living on this chessboard, one at (0,0), one at (1,0) and the third ad (0,1). These blobs reproduce by splitting up. When a blob splits up, one half of it moves up one space (this space must be empty) and the other half moves right one space. The space of the original blob is now empty. This happens to exactly one of the blobs each second. The blobs cannot move in any other way.

In other words, a "move" consist of taking:
a blob on (x.y)
an empty space at (x+1,y)
an empty space at (x,y+1)
and turning it into:
an empty space at (x,y)
a blob on (x+1,y)
a blob on (x,y+1)

Make sense?

Now these three starting blobs live in their cosy home. The home consists of (0,0), (1,0) and (0,1). What is the minimum number of seconds it will take for the blobs to completely vacate their home?
2. 15 Jun '08 12:56
I'm discovering (not to my shock) that the chains of blobs are behaving in a manner similar to a ladder structure in Go, which promises to go on forever but which leaves a trail which stays in the way of pieces needing to split behind it.

It looks like this

00
000
-00

It turns into this

-00
0000
0-00
-00
3. sonhouse
Fast and Curious
15 Jun '08 20:11
Originally posted by Dejection
This problem is very similar to the last one. Hopefully many of you will be able to solve it!

Suppose we have the bottom left hand corner of a chessboard, and this chessboard extends up and to the left forever. Call the bottom left corner (0,0), the one to the right of that (1,0) and the one above that one (1,1) etc. You get the gist. Think of the first ...[text shortened]... t is the minimum number of seconds it will take for the blobs to completely vacate their home?
I think you mean from the lower left hand corner the board extends up and to the RIGHT, unless you are using some kind of higher dimensional space. Haven't you heard of the game "Life"? Very similar, except there are parents and pogeny.
4. 15 Jun '08 20:15
Originally posted by Dejection
This problem is very similar to the last one. Hopefully many of you will be able to solve it!

Suppose we have the bottom left hand corner of a chessboard, and this chessboard extends up and to the left forever. Call the bottom left corner (0,0), the one to the right of that (1,0) and the one above that one (1,1) etc. You get the gist. Think of the first ...[text shortened]... t is the minimum number of seconds it will take for the blobs to completely vacate their home?
Hint:

(1/2)^(x+y)
5. eldragonfly
leperchaun messiah
15 Jun '08 21:36
Originally posted by Dejection
In other words, a "move" consist of taking:
a blob on (x.y)
an empty space at (x+1,y)
an empty space at (x,y+1)
and turning it into:
an empty space at (x,y)
a blob on (x+1,y)
a blob on (x,y+1)

Make sense?

Now these three starting blobs live in their cosy home. The home consists of (0,0), (1,0) and (0,1). What is the minimum number of seconds it will take for the blobs to completely vacate their home?
there is a "collision" on the first cycle between blob (1,0) and blob (0,1). blob (0,0) is surrounded and cannot move.
6. 15 Jun '08 22:39
I must clear something up. Yes i did mean extends to the RIGHT forever. And no, there is no collision.

I said that each second ONE of the blob split. So just because the blob at (0,0) can't split to start with, it can later.

It is better to think of this not as life, but as a game where the aim is to split blobs until you clear their home. How many moves must you make?
7. 16 Jun '08 03:33
I thought about it afterwards, and similar to the other, you can place a value on the squares such that each move leaves you with the same total value, where the blob vacating and splitting splits onto two squares which have half the value each.

The sum value of the entire board thus labelled (assuming the 0,0 point has a value of 1) is:

sum(i=0 to inf, sum(j=0 to inf, 1/2^(i+j)))

The first row sums to 1 + 1/2 + 1/4 + 1/8 + ... = 2
The second row sums to half that and so forth and so on, making the entire board worth 2 + 1 + 1/2 + 1/4 + 1/8 + ... = 4

The home squares are worth 1 + 1/2 + 1/2 = 2, or half the value of the entire infinite board. So in order to vacate int starting 3 squares requires every other square be occupied, an infinite number of splits for an infiinite number of blobs.
8. 16 Jun '08 08:57
Nicely done geep!
9. eldragonfly
leperchaun messiah
16 Jun '08 18:544 edits
Originally posted by Dejection
I must clear something up. Yes i did mean extends to the RIGHT forever. And no, there is no collision.

I said that each second [b]ONE
of the blob split. So just because the blob at (0,0) can't split to start with, it can later.

It is better to think of this not as life, but as a game where the aim is to split blobs until you clear their home. How many moves must you make?[/b]
yes there is a collision, unless it is legal for two blobs to occupy the same square, in this case (1,1), which is what would happen if blob (0,1) and blob (1,0) moved after the first cycle.
After 1st move/1st cycle :
10. 16 Jun '08 19:14
Originally posted by eldragonfly
yes there is a collision, unless it is legal for two blobs to occupy the same square, in this case (1,1), which is what would happen if blob (0,1) and blob (1,0) moved after the first cycle.
[fen]8/8/8/8/8/P7/1P6/p1P5[/fen]
There is no collision because the second split cannot occur until both destination squares are unoccupied.

split (0,1) and you cannot split (1,0), because one of the destination squares is occupied.
split (1,1) and NOW (1,0) can be split.
11. eldragonfly
leperchaun messiah
16 Jun '08 19:353 edits
Originally posted by geepamoogle
There is no collision because the second split cannot occur until both destination squares are unoccupied.

split (0,1) and you cannot split (1,0), because one of the destination squares is occupied.
split (1,1) and NOW (1,0) can be split.
ðŸ˜•
no i'm talking from the initial starting position. blob (0,0) cannot move because of blob(0,1) and because of blob(1,0) both are occupying adjacent squares. When blob(0,1) and blob(1,0) move they both end up occupying the same square(1,1). This is what i was questioning, not the result of the second move or cycle. ðŸ˜
12. 16 Jun '08 19:52
If either of the destination squares already has a blob on it, that split cannot occur at that time.

In other words, both destination squares have to be empty at the time of the move in order for the move to occur.

Also, only one move occurs at a time, so you would start with one or the other (your choice), but not both at once. And whichever one you choose, the other has to remain until square (1,1) is clear.
13. eldragonfly
leperchaun messiah
16 Jun '08 19:531 edit
Originally posted by geepamoogle
If either of the destination squares already has a blob on it, that split cannot occur at that time.

In other words, both destination squares have to be empty at the time of the move in order for the move to occur.

Also, only one move occurs at a time, so you would start with one or the other (your choice), but not both at once. And whichever one you choose, the other has to remain until square (1,1) is clear.
so you are saying that either blob(0,1) or blob(1,0) can move but not both on the first cycle.
14. 16 Jun '08 23:27
Precisly (is that how you spell it?)
15. 17 Jun '08 10:34
Originally posted by Dejection
Precisly (is that how you spell it?)
no

now im starting to wonder on ur english exam....