# The Human Invasion

**Discrete Mathematics**Level 5

Humans have invaded the Cartesian plane! They have eliminated most of the native residents, the ants. The few remaining ants are tortured and experimented on. One of the ants, Brilli the ant, has broken out from a human jail.

Brilli the ant comes to the origin, where she learns from the Oracle that in order to fend the humans off, she has to steal an extremely powerful weapon known as the WolframAlpha which is located at a particular lattice point on the positive \(x\)-axis. Meanwhile, the humans have located Brilli and have placed guards on every lattice point (points with integer coordinates). In order to avoid getting detected by the motion sensors set up by humans, Brilli can't move along any line parallel to either of the axes. Each minute, she can

- either move one unit up, one unit right,
- move one unit up, one unit left,
- or move one unit down, one unit right.

Furthermore, she has to bribe \($1\) every guard she comes across, so every time she takes a move, she has to spend \($1.\) To avoid suspicion, she can't visit the same point more than once. Also, since the second, third, and fourth quadrants are heavily guarded by humans, Brilli the ant has to stay entirely within the first quadrant (she can touch the \(x\)- and \(y\)-axes, though).

Ironically, the shorter the route Brilli takes to the WolframAlpha, the greater the chances are of humans detecting her, so she takes the longest route possible. If at any point she runs out of money, she is caught by humans because humans rarely show any act of compassion unless bribed.

Suppose Brilli has \($2014\) in her pocket, so she can visit \(2014\) points at most. The WolframAlpha is located at point \((k-1, 0),\) where \(k\) is a positive integer.

Find the largest value of \(k,\) such that no matter which route Brilli the ant takes (she takes the longest possible route, remember?), she ends up at the WolframAlpha with a positive amount of money.

**Details and assumptions**

To be specific, if Brilli is on the point \((x,y),\) after her next move, she can move to any of the points \((x+1, y-1), (x-1, y+1), \) or \((x+1, y+1)\) given that they lie on the first quadrant or one of the axes.

Brilli doesn't have to bribe the guard at the origin, but she has to bribe the guard who is guarding the point \((k-1,0).\)

As an explicit example, in the following figure (where the red point denotes the origin), Brilli the ant travels from the origin to the point \((4,0)\) in four moves. For this journey, she has to spend \($ 4.\)

No ants or humans were harmed in the making of this movie... err, sorry, problem.

The ending of this problem is intentionally left vague. You can, however, assume that ants win the game once Brilli makes it to the WolframAlpha.

This problem was inspired by a previous Brilliant problem.

There was a mistake in the original wording. I'm terribly sorry for this inconvenience.