This question has been written in order to help answer Fastest way to collect an arbitrary army.
There is a 1 x 1 square area with corners labelled clockwise A, B, C and D. A finite number of stationary robots are spread out across the area. Every robot knows where every other robot is at any time. A robot may only pass a message to another robot by touch. All robots travel with speed 1.
Robot Zero is at point A and receives the following message from an off grid source:
"Ensure that all robots leave the area as quickly as possible, through point C".
Given that we do not know how many robots there are or where they are:
What is the longest time it could take to clear the area of robots?
How can you prove it?
You can assume the following:
- Robots have negligible area, so when they touch in order to relay the message, they are occupying the same point on the square.
- Message is transferred in negligible time
- When faced with two options of equal efficiency a robot is able to make a decision (in collaboration with another robot where necessary) in negligible time. So, if there are two robots at B and there is only one other robot on the grid, at D, the two robots at B are able to send one robot to D to relay the message, while the other robot goes straight from B to C.
- The robots are all able to calculate the most efficient way of relaying the message to all robots.