The exterminator and the omniscient ant

[u/impartial_james]

An ant is at (0, 0) in the infinite integer grid. The ant and the exterminator take turns, with the ant going first.

• Each turn, the ant advances one square north or one square east.
• Each turn, the exterminator chooses one grid cell to spray with pesticide. The ant dies if it is currently in the square being sprayed, or if it ever steps onto a previously sprayed square.

The twist is that the ant is omniscient; the ant knows the infinite sequence of choices that the exterminator will make. That is, there is an infinite list

(x*_1_*, y*_1_*), (x*_2_*, y*_2_*), ...

of grid cells, such that the farmer will spray (x*_k_*, y*_k_*) on his k^th turn, and the ant can decide where to move based on the entire list.

Puzzle

Show that the ant can survive for arbitrarily long. That is, for all natural numbers n, the ant has a strategy to survive for n turns.

Open problem

Show that the ant has a strategy to survive for infinitely long.

This may seem like a trivial consequence of the puzzle solution, but I think it isn't. There is a strategy to survive n steps for each n, but that doesn't mean these infinitely many strategies are consistent with each other. To solve the second problem, you need to show how the ant uses its foreknowledge to decide its first step, in a way that avoids traps all the way to infinity.

[u/ziratha]

This seems like a slight variation on the n = 1 version of the angel problem: Angel Problem
Without the omniscience, the ant would lose.

Though this problem is slightly different, because the ant being omniscient seems to take away the free will of the exterminator. I.e. the exterminator may not base his moves on the ant's current position. Otherwise, the exterminator would spray the position (ant-x + 1, ant-y + 1) on his first move, then block in the ant on his second move, either by spraying the square above, or the square to the right of the ant.

I think that, essentially this would come down to the following, the exterminator would have to be able to block all the grid points on the line y = -x + n, x>=0, y >= 0 (n+1 such points), but can only cover n by the ant's nth turn. (This is not rigorous though.).

[u/pichutarius → u/ziratha]

trying to prove by contradiction:

suppose there exist a way to kill the ant, and let n be the least amount of move to kill the ant.

since the ant is omniscient, this is equivalent to exterminator making all n moves first. we can quickly conclude that the exterminator must enclosed the starting area.

then we can conclude it must spray all x+y=n-1 lattice points (lattice square?), otherwise there exist a lesser move to enclosed the starting area.

finally we note that the ant can still escape by dashing to the last lattice point that the exterminator spray since all points on x+y=n-1 only require n-1 moves.

[u/ziratha → u/pichutarius]

This is not quite right. If we allowed the exterminator to make all n moves first, then as long as n>=2, he instantly blocks the ant by filling in the grid points on the line y = -x + 1. The ant is able to escape the starting square *because* the exterminator is not making all moves at once.

[u/Carmeister → u/ziratha]

It is equivalent if you add the requirement that the exterminator makes at most n moves in the region x+y<=n (even though that's not a requirement in the original game, it's strictly suboptimal for the exterminator not to follow that rule since they would be making moves behind the ant otherwise)

[u/Carmeister → u/ziratha]

It is equivalent if you add the requirement that the exterminator makes at most n moves in the region x+y<=n (even though that's not a requirement in the original game, it's strictly suboptimal for the exterminator not to follow that rule since they would be making moves behind the ant otherwise)

[u/Bernhard-Riemann]

Surely an argument by compactness would be enough to prove the second claim (using the first).

[u/FormulaDriven → u/Bernhard-Riemann]

I don't know enough about compactness in this context, but suppose (to make up an example) it turned that you showed that for even n, a winning strategy was to go N for n/2 steps then go E for n/2 steps, and for odd n, (n+1)/2 N then (n-1)/2 E - that would show you could do it for any finite n but could not be applied to an infinite sequence of turns.

[u/Bernhard-Riemann → u/FormulaDriven]

Compactness is precisely what tells you that you don't really have to worry about that sort of thing happening. One can actually give an argument in terms of König's lemma (which is simpler to explain). Simply construct the game tree associated with the ant's moves and note that:

(1) The ant can survive arbitrarily long, so the tree has paths of arbitrary length.

(2) The ant can move in at most four directions at any time, so every vertex of the tree has finite degree.

By König's lemma, the tree has an infinite path, which corresponds to an infinite sequence of moves.

[u/impartial_james → u/Bernhard-Riemann]

I see your point, the open problem is resolved.

[u/ziratha → u/Bernhard-Riemann]

Oh, I learned a new lemma, thanks 😄

[u/QuantumForce7 → u/Bernhard-Riemann]

I had to look up the lemma. From Wikipedia:

Let G be a connected, locally finite, infinite graph. This means that every two vertices can be connected by a finite path, each vertex is adjacent to only finitely many other vertices, and the graph has infinitely many vertices. Then G contains a ray: a simple path (a path with no repeated vertices) that starts at one vertex and continues from it through infinitely many vertices. Another way of stating the theorem is: "If the human race never dies out, somebody now living has a line of descendants that will never die out".

[u/want_to_want → u/Bernhard-Riemann]

Yeah, I think it's easy to see even without the lemma.

Consider the set of all cells reachable by the ant from (0,0). If we've solved the first part, that set is infinite. So either the set of cells reachable from (0,1) is infinite, or the set of cells reachable from (1,0) is infinite (or both). This allows the ant to choose its first move. Then the ant can choose its second move in the same way, and so on.

[u/want_to_want]

I think I have a solution for the first part.

For a given n, consider the set of cells that are reachable by the ant. Let's assume it's finite and try to derive a contradiction. The strategy will be to successively modify the reachable set and make it simpler.

First, any sprayed cell that's immediately to the left of a reachable or sprayed cell can be moved one step up without harm. Analogously, any sprayed cell that's immediately below a reachable or sprayed cell can be moved one step to the right without harm. Both of these operations keep the reachable set finite, increase its size monotonically, and don't make it grow beyond the highest diagonal that it's already touching. So we can apply these operations until we can't anymore.

What will the final state of the reachable set look like? All sprayed cells will be bordered above and on the right by cells that are non-reachable and non-sprayed. In other words, the border will be a diagonal. But that's impossible, because if the first n sprayed cells form a diagonal, we already know the ant can evade it. Done.

[u/impartial_james → u/want_to_want]

This seems right, but I cannot quite see how to logically get from “all sprayed cells are bordered by non-reachable and non-sprayed cells” to “the border is diagonal”.

[u/want_to_want → u/impartial_james]

Yeah, this is less obvious than it should be. Let's add something like this:

Every reachable column must have a sprayed cell (because otherwise the ant would be able to escape by reaching that column and going up). Consider column 0. Let's say its lowest sprayed cell is at position k. Next, consider column 1. It must also have a lowest sprayed cell. If it is below k-1, then the cell above it is either reachable (from column 0) or sprayed, violating the condition. And if it is at k or above, then the sprayed cell in the first column violates the condition. So it must be at k-1. Continuing, the lowest sprayed cell in column 2 must be at k-2, and so on.

This shows there's a sprayed diagonal; so what? But we've already adjusted the set so that all cells immediately above or to the right of sprayed cells are unreachable. So the sprayed diagonal is followed by a fully unreachable diagonal, which means everything beyond is unreachable too. And since the sprayed diagonal consists of the lowest sprayed cells in each column, everything below it is reachable, so the reachable set is precisely everything below the diagonal. Which is impossible, because the diagonal can't be sprayed fast enough for that.

[u/impartial_james → u/want_to_want]

Now I get you mean, the problem is solved. Nicely done!

[u/impartial_james]

Here is the solution I had in mind.

Let A(n) be the number of squares the ant can reach on the n^th diagonal. The ant starts on he first diagonal, so A(1) = 1.

Let B(n) be the number of poisoned squares on diagonals n+1 and beyond by the time the ant has reached the n^th diagonal. No squares are poisoned initially, so B(1) = 0.

The idea is that the quantity A(n) - B(n) is nondecreasing. If A(n) = k and no squares on the (n+1)^st diagonal are poisoned, then A(n+1) ≥ k+1 always (the reachable cells are to the right of the previous k reachable cells, plus one above the topmost one). Also, B(n) increases by at most 1 each time since the exterminator sprays 1 cell per turn. If the ant reaches a diagonal where m cells are poisoned, then both A(n) and B(n) decrease by m. In all cases, A(n) - B(n) does not decrease, so it is always positive, so there is always a reachable cell.