Another puzzle

[jason_t]

I love this forum's new found fascination with puzzles. It's pulling us out of the dark ages of obsession with religion. So now I will post one of my all-time favorites. I posted this a long time ago in OOT but no one solved it.

Here's a two-way infinite chessboard with a blue dot in its lower left corner.



The board streches infinitely far up, and infinitely far to the right.

The idea is to obtain a configuration with no blue dots behind the bold black line. You move pieces as follows. If a square with a blue dot in it has the square above it and to the right of it free of blue dots, then you can remove the blue dot from the original square and place blue dots in the squares above and to the right of the original square. Therefore



becomes



Your goal is to make such moves over and over to free the region behind the bold line of blue dots.

Please post solutions in white and don't post if you have already seen a solution to this puzzle before.

[PairTheBoard]

Begin White
<font color="white">
I must be missing something. Using co-ordinates, you have blue dots progressing up and to the right and out of the way.

(1,1)
(2,1) (1,2)
(2,1) (2,2) (1,3)
(2,1) (2,2) (2,3) (1,4)
(2,1) (2,2) (2,3) (2,4) (1,5)
(2,1) (2,2) (2,3) (3,4) (2,5) (1,5)
(2,1) (2,2) (3,3) (2,4) (4,4) (3,5) (2,5) (1,5)
move (3,5) to (4,5)(3,6)
move (2,5) to (3,5)(2,6)

ok so it's getting pretty messy. But just keep moving stuff in the way up and out until there's room to get the last dots out. Does something prevent this?

</font>
End White

PairTheBoard

[jason_t]

If it were that simple, the question wouldn't be interesting.

[PairTheBoard]

I'm not doing anything against the rules am I?

PairTheBoard

[jason_t]

[ QUOTE ]
I'm not doing anything against the rules am I?

PairTheBoard

[/ QUOTE ]

No, all of your moves are valid.

[chiachu]

at first glance id like to think i could just select blue dots to push them outwards until they are all on the other side of the black line... but jason says this is his favorite puzzle, so there is no way this can be the answer [img]/images/graemlins/frown.gif[/img]

Im about to go to sleep, so ill think about this tomorrow at work, then come back and demand a solution [img]/images/graemlins/grin.gif[/img]

random note: i just read the other puzzles posts and solutions from the last few days, and i must say: jason you are one crazy mofo

[Jake (The Snake)]

<font color="white"> I thought about this one for a good long time and I don't see a solution. In order to simplify, I took away one of the resulting two dots, leaving just the dot on 1,2. I can't find a pattern that would work with just the one dot, as there will always be one dot left over on 2,3 or 3,2. Hopefully I'm not retarded and there is no solution, but I'm not hopeful. </font>

[sirio11]

<font color="white"> The idea for the solution is based in the example about clearing the first 3 diagonals.
To clear the first 3 diagonals, we need to "accommodate" 2^3=8 points. We can accommodate at most 4 in the 4th diagonal, so we have 4 points left. Since these 4 points "jump" to the 5th diagonal, now we need to accommodate 4(2)=8 points; we can accommodate 5 points in the 5th diagonal, now we have 3 left, so we need to accommodate 3(2)=6 points in the 6th diagonal, and since we have 6 spaces, there is no contradiction here.

Now the solution:

Let f(n) be the number of points left to accommodate in diagonal n+1 after using all the spaces in diagonal n.

since we need to accomodate 2 f(n) (because of the "jump") in diagonal n+1

We have the relation f(n+1) = 2f(n) - (n+1)


therefore, if 2 f(n) &gt; n+1 for all n we have a contradiction (we have always more points than spaces). Lets call this Condition M.

Let suppose there exist n such that

f(n) &gt; n+2

therefore 2f(n) &gt; 2n+4

2f(n) - (n+1) &gt; 2n+4 - (n+1)

f(n+1) &gt; (n+1) + 2


Also if f(n) &gt; n+2

then 4f(n) &gt; 4n+8 &gt; 3n+4

then 4f(n) &gt; 2(n+1)+n+2

2[2f(n)-(n+1)] &gt; n+2

2f(n+1)&gt; (n+1)+1 ......... condition M

Now, since to clear the first 4 diagonals, we need to accommodate 16 points, f(5)= 16-5 = 11 &gt;5+2

Therefore it is impossible to clear the firs4 4 diagonals.

(Notice how in the case with 3 diagonals, f(4)= 8-4 = 4 not greater than 4+2) </font>

[Timer]

[ QUOTE ]
I love this forum's new found fascination with puzzles. It's pulling us out of the dark ages of obsession with religion. So now I will post one of my all-time favorites. I posted this a long time ago in OOT but no one solved it.

Here's a two-way infinite chessboard with a blue dot in its lower left corner.





[/ QUOTE ]

Does this game have a name, and is there a web site where you can play this game using a computerized grid, so that you don't have to make your own and do all of the erasing, etc.?

[jason_t]

[ QUOTE ]
Does this game have a name, and is there a web site where you can play this game using a computerized grid, so that you don't have to make your own and do all of the erasing, etc.?

[/ QUOTE ]

Not that I am aware of.