Problem 9 Solution: The Killing Fields

Problem 9a.

Suppose that there exists a strategy S that always succeeds with less than N deaths. Suppose that the worst case number of deaths with strategy S is K, and consider an arrangement of kill zones that leads to K deaths. This means that the first K attempts hit a kill zone, and attempt number K+1 gets through. Now move one of the kill zones that didn't get hit (this must exist since K<N) into the path of attempt K+1 (shrinking it as necessary so it doesn't hit paths from other attempts). Then S won't notice anything different until it's too late, because the algorithm didn't hit that kill zone before and won't hit that kill zone this time until attempt K+1, which will hit it. Thus this algorithm will take at least K+1 deaths on this new arrangement, contradicting the assumption that K was the worst case number.

Problem 9b.

Go up in a straight line. If you hit a kill zone, mark a circle of radius 2 around that point - this is the "danger zone" for that kill zone. You know that the kill zone you hit lies entirely within the danger zone, because the center of the kill zone is at most 1 away from where you got hit, and any point in the kill zone is within 1 of the center. Then make another attempt, but this tim maneuver to avoid the danger zone. If you get hit mark another danger zone, and try again avoiding all danger zones marked so far.

This technique will ensure that you never hit the same kill zone more than once. However we still need to show that it will actually get you to the top. Since each danger zone has diameter 4, the sum of the diameters of all the danger zones is equal to 4N which is less than X, so there isn't enough space for the danger zones to completely block the path to the top, so you will be able to get to the top.

Problem 9c.

This is a trick question: there is no limit. If N > X/2, the defender can position his kill zones in a line across the middle, and since the sum of the diameters of the kill zones is 2N which is greater than X, he can completely block the entire path up, so the attacker will never be able to get to the top.