The army of ants

[bonanova]

An infinite army of ants comprises soldiers with integer coordinates on the lower half-plane including the x-axis (non-positive values of y.) The army advances upward by jumping over adjacent comrades to unoccupied positions. The y-value of the jumping ant thus increases by 2. The comrade, however, is killed in the process and removed from battle. The effect is like moves in checkers, where the jumped checker is removed, except that the ants may advance vertically as well as diagonally forward. Horizontal jumps are also permitted, but no ant may retreat. To win the war, an ant must reach an enemy stronghold somewhere in the upper half plane. Can the ants advance to arbitrarily large values of y?

 

Example of a jump to the northeast:

                                                       x
------ x x x x x x x x x x ---  x-axis --- x x x x x . x x x x -------
   ... x x x x x x x x x x ...         ... x x x x . x x x x x ...
   ... x x x x x x x x x x ...         ... x x x x x x x x x x ...
   ... x x x x x x x x x x ...         ... x x x x x x x x x x ...
   ... x x x x x x x x x x ...         ... x x x x x x x x x x ...
   ... x x x x x x x x x x ...         ... x x x x x x x x x x ...
   ... x x x x x x x x x x ...         ... x x x x x x x x x x ...
   ... x x x x x x x x x x ...         ... x x x x x x x x x x ...
   ... x x x x x x x x x x ...         ... x x x x x x x x x x ...
   ... x x x x x x x x x x ...         ... x x x x x x x x x x ...
   ... x x x x x x x x x x ...         ... x x x x x x x x x x ...
   ... x x x x x x x x x x ...         ... x x x x x x x x x x ...

Edited August 12, 2014 by bonanova
Show jump

[plasmid]

Think about the problem backwards. Define the target y-coordinate as 1 and have the army of ants start at a y-coordinate of N and occupy all spaces from N upward, and they'll move downward to reach a y-coordinate of 1.

After the final step of a solution, you would have an ant at y-coordinate 1.

Just before the final step of a solution, you need an ant at y-coordinate 2 who will be jumped by an ant at y-coordinate 3.

Just before that, you either need (if an ant will make a jump to reach y-coordinate 2 for the next step) two ants at y-coordinate 3 and one ant at y-coordinate 4 who will jump to y-coordinate 2, or (if an ant will make a jump to reach y-coordinate 3 for the next step) one ant already at y-coordinate 2 and one ant at y-coordinate 4 and one at y-coordinate 5.

Using that logic I will start re-writing those as ordered lists to make things more compact. After the final step, you have [1, 0, 0, 0...]. Just before that, you have [0, 1, 1, 0, 0...]. Just before that, you have either [0, 0, 2, 1, 0, ...] or [0, 1, 0, 1, 1, 0, ...]. It should be clear that, to get an ant to coordinate N, you must use two ants at coordinates N+1 and N+2 in the preceding move.

The problem could be rephrased as: could you do a bunch of moves (backwards like this) to reach a state [0, 0, 0, ... 0, Z, Z+1, Z+2, ...] that starts with Z zeros? The number of available ants starting at index number Z is equal to Z because you can think of this as a puzzle where, if the final square that an ant occupies after running through a solution is e.g. black if we color the grid like a chessboard, then only the ants on black squares within a 90 degree cone of the final square could contribute to the solution, and the number of such black squares increases by 1 for every row out you go.

Suppose you start at [1, 0, 0, 0, ...] and try to clear out as many rows with zeros as possible. You could go [0, 1, 1, 0, 0, ...], followed by [0, 0, 2, 1, 0, 0, ...]. Then to get those two ants at the third index you would have come from [0, 0, 0, 3, 2, 0, 0, ...]. Then it would be [0, 0, 0, 0, 5, 3, 0, ...]. So far so good, if you had the army of ants starting at row #5 then you do have five ants in that row followed by 3 ants in row 6.

But if you push things out another step, you get [0, 0, 0, 0, 0, 8, 5, 0, ...]. Now you need to take 8 ants from row #6 but you only have six ants that start out there. It could still be solvable if you have one of those ants starting at row #6 be used, either getting jumped or doing some jumping, and then have it replaced by an ant from farther down. If you had two such ants, you could get there from [0, 0, 0, 0, 0, 6, 7, 2, 0, ...].

Now to try to clear out the sixth row. You would need [0, 0, 0, 0, 0, 0, 13, 8, 0, ...]. Again, to get 13 ants to row #7 you would need to "borrow" some ants from further down: [0, 0, 0, 0, 0, 0, 7, 14, 6, 0, ...]. But now we need too many ants from row #8, so time to borrow some more: [0, 0, 0, 0, 0, 0, 7, 8, 12, 6, 0, ...]. Now row #9 is in trouble. [0, 0, 0, 0, 0, 0, 7, 8, 9, 9, 3]. That works. Phew.

Dare we try to clear out the seventh row?

We get [0, 0, 0, 0, 0, 0, 0, 15, 16, 9, 3, 0, ...].

Then [0, 0, 0, 0, 0, 0, 0, 8, 23, 16, 3, 0, ...]

Then [0, 0, 0, 0, 0, 0, 0, 8, 9, 30, 17, 0, ...]

Then [0, 0, 0, 0, 0, 0, 0, 8, 9, 10, 37, 20, 0, ...]

Then [0, 0, 0, 0, 0, 0, 0, 8, 9, 10, 11, 46, 26, 0, ...]

Then [0, 0, 0, 0, 0, 0, 0, 8, 9, 10, 11, 12, 60, 34, 0, ...]

That number looks like it's just going to keep growing as you try to push it back and there won't be a way to clear out the seventh row.

[Quantum.Mechanic]

I saw this puzzle in the same Peter Winkler book I mentioned elsewhere.

His "solution" was unsatisfying, relying on some metric which scores ants above the X-axis, and higher for ants higher above the axis, and closer to the Y-axis. Since it's the infinite half-plane, it should make no difference what the X coordinate is.

I'd suggest yes, it's possible to do any arbitrary height, though I have no solid proof.

But if as in your example, we can get any ant above the X-axis, then it is fairly trivial to fill in below it, and allow a jump to a higher Y value. Sure, the devil is in the details for replacing all the jumped ants, which must come from farther and farther away. So this may end up being extremely tedious in the vein of Towers of Hanoi. Or I may be completely wrong, and it's not possible, due to backfilling all of the missing ants at an exponential rate which is faster than the growth in height above the X-axis.

 

I feel another program coming on...

[bonanova]

the x-dependence was introduced so that the objective function would be a convergent series. The point is the effect of a jump. In configuration space you advance two levels at the cost of two holes. Can the void of two empty slots be filled efficiently enough to allow arbitrarily many jumps to greater y-values? It's not immediately clear, But an objective function would say. And it seems to say no.

It's unsatisfying in that it does't show the configurational detail. But it is elegant in that it answers the question without having to analyze the detail. Or, the effect of a jump on the objective function answers the question without having to analyze the effect of a jump on the configuration. A proof that a math person appreciates much more than an engineer (e.g. myself) does.

I hoped that posing the question here would produce some analysis at the configuration level. Let's see if it does.

[bonanova]

Can we deduce from this an upper limit on y (for the OP)?

[plasmid]

Converting my numbering to the type of numbering that would be used in the OP, my answer implies that if ants start off at y=0 and no higher, then they won't be able to reach y=7. It doesn't ensure that they can somehow reach y=6, it just doesn't rule it out as impossible.

[bonanova]

It would be interesting compete with a list of moves that gets to the "highest" y-value.

Earlier solvers disallowing diagonal moves could get only to y=4.

I've played with this but it gets complicated too quickly.

[plasmid]

Actually, I overlooked that the OP said the ants can jump straight vertically and straight horizontally as well as diagonally. That makes my omission of ants on the opposite color square as the final goal if the grid is colored like a checkerboard (they can contribute to a solution by being jumped), and my counting of only ants that are within a 90 degree cone of the goal (ants can jump horizontally to enter such a cone and contribute to an answer) invalid.

[plasmid]

Allowing straight vertical jumps will mean that ants that are on the opposite color square as the goal (if the grid is colored like a chessboard) can contribute to the solution, so instead of having N ants available on row N within the 90 degree cone from the goal, you'll have 2N-1 ants available.

Taking into account the possibility of horizontal jumps, you could get two extra ants into the 90 degree cone from the goal by having an ant just outside the cone get jumped horizontally by an ant that's two spaces outside the cone. Pictorially,

X X X X X X/X X X\X X X
          /       \    
X X X X>X/  X X X X\X X
        /           \  
X X X X/X X X X X X X\X
      /               \
X X X/X X X X X X X X X

goes to

X X X X X X/X X X\X X X
          /       \    
X X X    /X X X X X\X X
        /           \  
X X X X/X X X X X X X\X
      /               \
X X X/X X X X X X X X X

That will get you two extra ants into a row's cone - one from each side. You could also get another two ants into that row of the cone by having the ants just outside the border of the cone jump up two rows into the vacated spaces to get

 

X X X X X X/X X X\X X X
          /       \    
X X X X X/X X X X X\X X
        /           \  
X X    /X X X X X X X\X
      /               \
X    /X X X X X X X X X

followed by another lateral jump into the cone, but then you would give up two ants that could have entered the cone on rows N+1 and N+2, and could have jumped each other after getting into the cone on their original rows to produce the same outcome. So for all practical accounting purposes, we can say that allowing lateral jumps will put two extra ants into each row.

So the number of ants available on each row goes from N (originally) to 2N-1 (taking into account vertical jumps) to 2N+1 (taking into account horizontal jumps). But the way of calculating the number of ants needed on each row remains the same.

It goes from

[1, 0, 0, 0, ...]

[0, 1, 1, 0, ...]

[0, 0, 2, 1, 0, ...]

[0, 0, 0, 3, 2, 0, ...]

[0, 0, 0, 0, 5, 3, 0, ...]

[0, 0, 0, 0, 0, 8, 5, 0, ...]

[0, 0, 0, 0, 0, 0, 13, 8, 0, ...]

[0, 0, 0, 0, 0, 0, 0, 21, 13, 0, ...] which is where we start having to borrow ants from later rows

[0, 0, 0, 0, 0, 0, 0, 17, 17, 4, 0, ...]

clearing out one more row gives

[0, 0, 0, 0, 0, 0, 0, 0, 34, 21, 0, ...] which becomes

[0, 0, 0, 0, 0, 0, 0, 0, 19, 36, 15, 0, ...] which becomes

[0, 0, 0, 0, 0, 0, 0, 0, 19, 21, 30, 15, 0, ...] which becomes

[0, 0, 0, 0, 0, 0, 0, 0, 19, 21, 23, 22, 7, 0, ...] ok

going for one more

[0, 0, 0, 0, 0, 0, 0, 0, 0, 40, 42, 22, 7, 0, ...] becomes

[0, 0, 0, 0, 0, 0, 0, 0, 0, 21, 61, 41, 7, 0, ...] becomes

[0, 0, 0, 0, 0, 0, 0, 0, 0, 21, 23, 79, 45, 0, ...] becomes

[0, 0, 0, 0, 0, 0, 0, 0, 0, 21, 23, 25, 99, 54, 0, ...] becomes

[0, 0, 0, 0, 0, 0, 0, 0, 0, 21, 23, 25, 27, 126, 72, 0, ...]

And that's destined to explode, so you won't be able to clear out 9 rows. Or alternatively, if you start with ants on the x-axis (at y=0) and no higher, they shouldn't be able to reach row 9.

[bonanova]

Allowing straight vertical jumps will mean that ants that are on the opposite color square as the goal (if the grid is colored like a chessboard) can contribute to the solution, so instead of having N ants available on row N within the 90 degree cone from the goal, you'll have 2N-1 ants available.

Taking into account the possibility of horizontal jumps, you could get two extra ants into the 90 degree cone from the goal by having an ant just outside the cone get jumped horizontally by an ant that's two spaces outside the cone. Pictorially,

X X X X X X/X X X\X X X
          /       \    
X X X X>X/  X X X X\X X
        /           \  
X X X X/X X X X X X X\X
      /               \
X X X/X X X X X X X X X

goes to

X X X X X X/X X X\X X X
          /       \    
X X X    /X X X X X\X X
        /           \  
X X X X/X X X X X X X\X
      /               \
X X X/X X X X X X X X X

That will get you two extra ants into a row's cone - one from each side. You could also get another two ants into that row of the cone by having the ants just outside the border of the cone jump up two rows into the vacated spaces to get

 

X X X X X X/X X X\X X X
          /       \    
X X X X X/X X X X X\X X
        /           \  
X X    /X X X X X X X\X
      /               \
X    /X X X X X X X X X

followed by another lateral jump into the cone, but then you would give up two ants that could have entered the cone on rows N+1 and N+2, and could have jumped each other after getting into the cone on their original rows to produce the same outcome. So for all practical accounting purposes, we can say that allowing lateral jumps will put two extra ants into each row.

So the number of ants available on each row goes from N (originally) to 2N-1 (taking into account vertical jumps) to 2N+1 (taking into account horizontal jumps). But the way of calculating the number of ants needed on each row remains the same.

It goes from

[1, 0, 0, 0, ...]

[0, 1, 1, 0, ...]

[0, 0, 2, 1, 0, ...]

[0, 0, 0, 3, 2, 0, ...]

[0, 0, 0, 0, 5, 3, 0, ...]

[0, 0, 0, 0, 0, 8, 5, 0, ...]

[0, 0, 0, 0, 0, 0, 13, 8, 0, ...]

[0, 0, 0, 0, 0, 0, 0, 21, 13, 0, ...] which is where we start having to borrow ants from later rows

[0, 0, 0, 0, 0, 0, 0, 17, 17, 4, 0, ...]

clearing out one more row gives

[0, 0, 0, 0, 0, 0, 0, 0, 34, 21, 0, ...] which becomes

[0, 0, 0, 0, 0, 0, 0, 0, 19, 36, 15, 0, ...] which becomes

[0, 0, 0, 0, 0, 0, 0, 0, 19, 21, 30, 15, 0, ...] which becomes

[0, 0, 0, 0, 0, 0, 0, 0, 19, 21, 23, 22, 7, 0, ...] ok

going for one more

[0, 0, 0, 0, 0, 0, 0, 0, 0, 40, 42, 22, 7, 0, ...] becomes

[0, 0, 0, 0, 0, 0, 0, 0, 0, 21, 61, 41, 7, 0, ...] becomes

[0, 0, 0, 0, 0, 0, 0, 0, 0, 21, 23, 79, 45, 0, ...] becomes

[0, 0, 0, 0, 0, 0, 0, 0, 0, 21, 23, 25, 99, 54, 0, ...] becomes

[0, 0, 0, 0, 0, 0, 0, 0, 0, 21, 23, 25, 27, 126, 72, 0, ...]

And that's destined to explode, so you won't be able to clear out 9 rows. Or alternatively, if you start with ants on the x-axis (at y=0) and no higher, they shouldn't be able to reach row 9.

 

 

That looks right. Nice work.