There is an infinite chessboard...

Originally posted by geepamoogle
Let me clarify that rule.

3) A piece cannot jump multiple pieces in a single move.


This leaves open the possibility of the piece jumping several others one at a time, which is very clearly a necessity to move beyond 1 row out.

Your statements are contradicting each other geepamoogle. It's easier to let the pieces move like checker pieces when they move and/or capture with the added condition of removing pieces as they are jumped, just not in a diagonal direction.

Originally posted by geepamoogle
I seem to recall hearing about this little problem from somewhere.

Now let me get this right.

[b]Move Rules
1) A piece may jump a piece orthogonally adjacent to it, provided the space beyond it is empty.
2) A piece that is jumped is removed from the board.
3) A piece cannot jump multiple pieces.
4) A piece cannot jump diagonally.
5) A piec ...[text shortened]... ing very cumbersome.

I wish I had a more complete answer, but perhaps someone else here does.[/b]

I found a solution to the fourth rank aspect of the problem which only requires 20 pieces and can be done on a chess board (assuming I understand the rules properly). This makes me doubt that a 5th rank is impossible to reach.

I have a diagram down on paper, but it would be difficult to draw. I suppose chess notation could be used...ugh.

First, c3-c5, removing c4. achieving a piece on the first rank
2) a4-c4,
3) c4-c6, piece on the second rank
4) e4-c4,
5) e3-c3,
6) c3-c5,
7) c5-c7, now we have a piece on the third rank (8 pieces to get here)
Now we want to get a piece back to c5, and another on c4
8) a2-a4,
9) b2-b4,
10) a4-c4,
11) c1-c3,
12) c3-c5, first goal accomplished,
13) e1-e3,
14) f3-d3,
15) d2-d4,
16) g4-e4,
17) e4-c4, second goal
18) c4-c6,
19) c6-c8, Yay, a fourth rank piece!

It seems hard to believe that with an infinite number of pieces one could not get to the fifth rank.

Originally posted by eldragonfly
Your statements are contradicting each other geepamoogle. It's easier to let the pieces move like checker pieces when they move and/or capture with the added condition of removing pieces as they are jumped, just not in a diagonal direction.

There is nothing in the rules as I stated them (for my own clarification, including the slight altering of Rule #3 to make it clearer) that would prevent the same piece from making several consecutive jumps in a row, with each jump being its own move.

What Rule #3 does prevent is a jump of 2 or more pieces in line without a gap between them, which is not allowed in peg solitaire (which is the basis of this little puzzle's physics). It wouldn't be allowed in checkers either.

Had I made a mistake in trying to restate how it worked, the Puzzle Poser was free to correct me, and I would have attempted to understand what false assumption or reading was made, and could then attempt to correct myself.

Remember with these problems, the Puzzle Poser is normally the final authority on what was intended.

Yes. If you can get a piece over the line, then you can get a piece to the second rank over the line. And if you can get a piece to the second rank over, then you can get a piece to the third rank over. If you can get a piece to the third etc...

I think it's possible.

Originally posted by geepamoogle
There is nothing in the rules as I stated them (for my own clarification, including the slight altering of Rule #3 to make it clearer) that would prevent the same piece from making several consecutive jumps in a row, with each jump being its own move.

What Rule #3 does prevent is a jump of 2 or more pieces in line without a gap between them, which is ...[text shortened]... er with these problems, the Puzzle Poser is normally the final authority on what was intended.

i see what you mean. Multiple jumps are allowed not just capturing more than one piece in a single jump.

Originally posted by Coconut
Yes. If you can get a piece over the line, then you can get a piece to the second rank over the line. And if you can get a piece to the second rank over, then you can get a piece to the third rank over. If you can get a piece to the third etc...

I think it's possible.

How many pieces do you think you need to start off with?
XD

The answer is that getting to the fifth row is not possible with a finite number of pieces, and hence not possible within a finite number of moves. I'll post a proof later unless some one wants to have a crack at proving that.

Proof that getting to the fifth row is impossible with a finite number of pieces.

We use that golden ration, phi=(sqrt(5)+1)/2. We use the fact that phi^2=phi+1.

We assign a value to each square. Choose a square in the fifth row above the line that we are aiming for, and give it the value of phi^5. The square below it is phi^4, to the left that is phi^3, phi^2, phi, 1, phi^-1 etc. To the right of the phi^4 is phi^3, phi^2 etc.
In the row below that, we assign each square the value of the square above divided by phi. In other words, the power of phi decrease by one for every square we move away from the square we are aiming for.

Now consider the sum of the values of all the squares with pieces on them. A vertical jump upwards will leave this sum unchanged (this is becuase phi^2=phi+1), and a horizontal jump towards the center will also leave it unchanged. Any other jump will decrease this sum. So to end up with a piece on our goal square, the sum of our initial position (with everything below the line) must be greater than or equal to the value of our goal square, which is phi^5.

We now proceed to find the sum of the squares below the line. Using a sum of geometric series a few times, we find that the sum of everything below the line is phi^5. Therefore, to get a piece onto the fifth row, every single square below the line must be filled at the start. This is of course not finite, hence, the fifth row is not attainable within a finite number of moves.

Originally posted by Dejection
Proof that getting to the fifth row is impossible with a finite number of pieces.

We use that golden ration, phi=(sqrt(5)+1)/2. We use the fact that phi^2=phi+1.

We assign a value to each square. Choose a square in the fifth row above the line that we are aiming for, and give it the value of phi^5. The square below it is phi^4, to the left that is ph ...[text shortened]... is of course not finite, hence, the fifth row is not attainable within a finite number of moves.

what are you talking about.

Originally posted by eldragonfly
what are you talking about.

Why it is impossible to get to the fifth rank.
What part don't you get? I'll try to explain it better.

Originally posted by Dejection
Why it is impossible to get to the fifth rank.
What part don't you get? I'll try to explain it better.

The problem is stated as an infinite chess board with infinite pieces, if you can get a piece to the fourth rank and then one orthogonal to the third rank, then you would be able to get to the fifth rank.

Dejection's proof is very abstract, but let me see if I can explain the overall gist of it..

First off, the number he uses, phi, or the golden ratio has the unique property that it's square is exactly one more than the number itself.

Pick an arbitrary column to be a "center" column. We're aiming to move a piece on the fifth forward row of this column. The furthest point on the column is assigned a value of 1. For every space forward, the value of the square is multiplied by phi. For every square backward, it is divided by phi. For every square to the side of the column, the value is divided by phi.

What Dejection looks at is the sum value of the occupied squares, and the effect of any potential move has on it. For purposes of this analysis, the piece is worth the value of the square where it sits.

When a piece jumps forward, or towards the center, you remove a piece worth k and a piece worth k*phi, but add a piece worth k*phi^2, where k is the value of the least valuable square.

So the sum effect on the value of all pieces is:
k*phi^2 - k*phi - k
k*(phi^2 - phi - 1)
k*(phi^2 - (phi + 1))

But phi^2 = phi + 1, so the change is k*0 or nothing.

For jumps backwards or away from the center, you remove two higher value pieces for a loew valued one, and the sum decreases. The net result is that there is no way to increase the net value of all the pieces, only decrease it, and we need at least phi^5 value of pieces in order to have a piece on the fifth forward row.


Now... that's all well and good, but how does that have anything to do with anything? Well, suppose you filled the entire infinite chessboard behind the line with pieces, what would the sum of their value be?

You would need to solve this summation from where i = 0 to infinity:

(2 * i + 1) / (phi^i).

The first few terms are 1/phi^0 (1), 3/phi, 5/(phi^2), etc, etc..

Now Dejection did not do the math for this, but apparantly this inifinite sum has the finite value of phi^5, which means our filled infinite board is just enough to have a piece reach the fifth rank. Remove any piece, and it becomes impossible, because we don't have sufficient value of pieces to equal the value of a lone piece on the fifth rank.

Originally posted by geepamoogle
Dejection's proof is very abstract, but let me see if I can explain the overall gist of it..

First off, the number he uses, [b]phi, or the golden ratio has the unique property that it's square is exactly one more than the number itself.

Pick an arbitrary column to be a "center" column. We're aiming to move a piece on the fifth forward r ...[text shortened]... n't have sufficient value of pieces to equal the value of a lone piece on the fifth rank.[/b]

hmmmm...

Originally posted by eldragonfly
The problem is stated as an infinite chess board with infinite pieces, if you can get a piece to the fourth rank and then one orthogonal to the third rank, then you would be able to get to the fifth rank.

The thing is, you can't get a piece to the fourth rank AND the third rank.