Who Let The Ants Out?

Humans have invaded the land of ants, again! This time, they plan to torture the ants until all of them are dead. It's up to their savior, Brilli the ant, to rescue them from the barbaric humans.

The humans have invented a devious game of death for the ants to play. They place a certain number of ants on a 2014 × 2014 2014 \times 2014 grid with 201 4 2 2014^2 cells. Each cell is occupied by at most one ant. Each second, an ant moves according to the following rules.

  • Each second, an ant moves one unit towards north, south, east, or west.

  • If exactly two ants moving in the opposite direction meet, they both turn 9 0 90^{\circ} clockwise and keep moving.

  • If more than two ants meet, or two ants moving in the perpendicular direction meet, the ants don't change their direction.

  • An ant is unable to change its direction unless it collides with exactly another ant moving at the opposite direction.

  • The ants decide which way to move at the beginning of the game.

  • If an ant reaches an edge of the grid, the humans kill it.

The plus side is, the humans let the ants choose how many of the ants are going to play the game. Also, they let the ants choose the positions of the cells the players will be in at the beginning of the game.

Ants are well famed for their mathematical abilities. They thus devise a strategy which will let at least one of the players survive for the largest possible amount of time.

Brilli's timer is synchronized with the beginning of the game. As soon as the game starts, the timer is at t = 0. t= 0. As each second passes, the ants take their moves, and the count increases by 1. 1. Brilli's goal is to save at least one of the players. What is the maximum number of seconds she has?

Details and assumptions

  • If it takes T T seconds for all the ants to die, enter T 1 T-1 as your answer.

  • The ants don't break the rules of the game.

  • The ants get to choose where they place their players and how many players they place. They plan to place them in such a way that one of the players survives for as long as possible.

  • Dead ants don't get resurrected.

  • This problem is not original.


The answer is 3019.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Ivan Koswara
May 28, 2014

This is IMO Shortlist 2011 Problem C5 . A popular solution, also seeming to be the official solution, is a "triangle of death" solution, which can be read in the linked thread.

Hmm, for some reason the link doesn't seem to work. Strange.

The main idea in the solution, as already pointed out in the thread in AoPS (AoPS -> Community -> Contests -> IMO Shortlist -> 2011 -> C5), is to note that no two ants can collide in any of the four grey shaded regions shown in the figure below (I'm using a 9 × 9 9 \times 9 grid), where the size of the regions increase with each move.

Image link: http://s28.postimg.org/mhpba80od/Untitled.png Image link: http://s28.postimg.org/mhpba80od/Untitled.png

Corrected link: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=41&t=488628

Anis Abboud - 6 years, 12 months ago

Log in to reply

For some reason a semicolon gets inside the link when it's posted (t= becomes t;=), please open the link and remove the semicolon manually.

Anis Abboud - 6 years, 12 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...