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 grid with 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 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 As each second passes, the ants take their moves, and the count increases by 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 seconds for all the ants to die, enter 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.
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.
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.