Best Answer plasmid, 15 August 2014 - 07:05 AM

Spoiler for not invoking any sort of x-axis

Go to the full post
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.

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.