UncleEbenezer wrote:OK, a followup problem for the serious.
As the number of blank rows grows, overcrowding rapidly becomes an issue. Iterating from the easy solutions upwards would be straightforward if squares could be re-used, placing more than one piece on a square, and removing exactly one piece when it is jumped.
So instead of a square grid, consider an n-dimensional grid. n=1 is easy, this thread deals with n=2. What about a cubic grid? Being able to approach from an orthogonal direction enables us to extend the iterative approach (and exponential solution) at least one row further.
Can you prove, or find a counterexample, to UncleE's conjecture. Namely, that for an N-dimensional grid, the exponential solution extends to N+1 blank rows?
I think some care needs taking about the question. I assume that one is working in an N-dimensional half-space: in 2 dimensions, that means everything in a 1-dimensional subspace (the 'top row') and to one side of it. That gives us a natural ordering on the rows parallel to the top row - there's the row 1 away from the top row, the row 2 away from the top row, etc, which we call the second row, the third row, etc. In 3 dimensions, it means everything in a 2-dimensional subspace (the 'top plane') and to one side of it, and we similarly have a natural ordering on the planes parallel to the top plane - but we don't have any natural ordering on 1-dimensional rows. So talking about the first N planes being blank makes sense, but not similar talk about the first N rows. In 4 dimensions, it means everything in a 3-dimensional subspace (the 'top hyperplane') and to one side of it, and we have a natural ordering on the hyperplanes parallel to the top hyperplane, but not on the rows or the planes. So talking about the first N hyperplanes being blank makes sense, but not similar talk about the first N rows or the first N planes. And so on...
So I think the 3-dimensional question should be: The board consists of a 3-dimensional grid of cubelets centred at positions (x,y,z), with x, y and z all integers and z <= 0. The cubelets centred at points (x,y,0) form the top plane, the cubelets centred at (x,y,-1) form the second plane, the cubelets centred at (x,y,-2) form the third plane, etc, and moves consist of jumping a piece in the cubelet centred at (x,y,z) over a piece in the cubelet centred at any of (x,y,z+1), (x,y,z-1), (x,y+1,z), (x,y-1,z), (x+1,y,z) or (x-1,y,z) into an empty cubelet centred at (x,y,z+2), (x,y,z-2), (x,y+2,z), (x,y-2,z), (x+2,y,z) or (x-2,y,z) respectively, removing the jumped piece from the board. What's the smallest finite number of pieces required in a starting position from which it is possible to end up with a piece in the top plane, if the first H planes are required to be empty in the starting position?
And there are analogous questions for an N-dimensional half-space board with the first H (N-1)-dimensional hyperplanes being required to be empty. My partial solution, spoiler-protected:
As in my previous argument for the 2-dimensional case, label the top-hyperplane (hyper)cubelet that we will get a piece into with "0" and every other cubelet with the minimum number of orthogonal (but not diagonal) steps required to get from it to the cubelet labelled "0", and give a piece in a cubelet labelled "n" a score of t^n, where t = (sqrt(5)-1)/2 = 0.6180339887... Give a position a score equal to the sum of the scores of its pieces, and as before, every move made from a position either decreases its score or leaves it unchanged. Since we're aiming to get to a position with a piece in the "0" cubelet, our final position must have a score of at least t^0 = 1, so it is impossible to achieve that aim from any starting position with a score less than 1.
As before, the total score available from a row containing the "0" cubelet is 1 + 2t + 2t^2 + 2t^3 + 2t^4 + ... = t^(-3). A plane containing the "0" cubelet consists of such a row, two rows parallel to and 1 away from it, two rows parallel to and 2 away from it, two planes parallel to and 3 away from it, etc. Since each cubelet in a row parallel to and i away from the row containing the "0" cubelet has an available score that is t^i times that of the corresponding cubelet in the row containing the "0" cubelet, the total available score from such a row is t^i times the total available score from the row containing the "0" cubelet, i.e. t^(-3) * t^i. So the total available score from a plane containing the "0" cubelet is:
t^(-3) * (1 + 2t + 2t^2 + 2t^3 + 2t^4 + ...) = t^(-3) * t^(-3) = t^(-6)
For the three-dimensional board, that tells me that the total available score from the top plane is t^(-6). That from the second plane is t times that, from the third plane t^2 times that, etc, so the total score available from the entire board is:
t^(-6) * (1 + t + t^2 + t^3 + t^4 + ...) = t^(-6) * t^(-2) = t^(-8)
If we forbid starting with pieces on the top H planes, the cubelets we are allowed to use are basically those of an entire board, but each only allowed a score that is t^H times as much. So the total available score for the starting position is t^(-8) * t^H = t^(H-8). So if H >= 8, the total available score for the starting position is <= 1, and furthermore it can only equal 1 if H=8 and every cubelet in the planes below the top 8 is occupied by a piece. So for H >= 8, every finite starting position has a score less than 1, and so cannot move to a position containing a piece in the "0" cubelet. So the problem is unsolvable for the 3-dimensional board if 8 or more top planes are to be avoided by the starting position.
For the 4-dimensional board, an analogous argument says that the total available score from the top hyperplane is t^(-6) * t^(-3) = t^(-9), that the total available score from the whole board is t^(-9) * t^(-2) = t^(-11), and that if H >= 11, every finite starting position that avoids the top 11 hyperplanes has a score less than 1, and so cannot move to a position containing the "0" cubelet. And more generally, that argument extends to say that the question "On an N-dimensional half-space board, what's the smallest finite number of pieces required in a starting position from which it is possible to end up with a piece in the top (N-1)-dimensional hyperplane, if the first H (N-1)-dimensional hyperplanes are required to be empty in the starting position?" has no answer if H >= 3N-1 because there is no such starting position.
That's a partial solution because it only says that the question has no answer if H >= 3N-1, not whether it has an answer when H <= 3N-2, let alone what the answer is when it does have one. I have a strong impression that it always will have an answer when H <= 3N-2 - strong enough that I would dignify it with the description "conjecture". And indeed, I have a rough idea about how I might go about proving that conjecture - though I've got to do some work on that idea before I'll know whether it does indeed work out.
What the answer is when it exists may well be a harder problem - showing that an answer exists only involves exhibiting a suitable starting position with some number S of pieces, but showing that the answer is S involves both doing that and showing that no position with < S pieces is a suitable starting position, which I suspect is a significantly harder thing to do!
Gengulphus