Jump to content
BrainDen.com - Brain Teasers
  • 0

The army of ants


bonanova
 Share

Question

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 by bonanova
Show jump
Link to comment
Share on other sites

9 answers to this question

Recommended Posts

  • 0

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.

Link to comment
Share on other sites

  • 0

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...

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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. post-1048-0-84137600-1395017309.gif

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...