2
$\begingroup$

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?

and

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.
Improve this question
$\endgroup$
9
  • $\begingroup$ This is very similar to puzzling.stackexchange.com/questions/548/… $\endgroup$
    – Ross Millikan
    Jun 30, 2014 at 0:00
  • $\begingroup$ My answer to that question argues that the answer to this should be 2 but not quite as there could be one at ABC and D. This would require $1+\sqrt 2$ $\endgroup$
    – kaine
    Jun 30, 2014 at 1:51
  • $\begingroup$ $2 + sqrt{2}$ ? I agree. My theory is that Robot Zero should be able to go from A to C along the critical path and always be increasing its direct distance to A, but I can't prove it... $\endgroup$
    – Ali
    Jun 30, 2014 at 8:54
  • $\begingroup$ @Ali I believe you could probably prove that $2 + sqrt(2)$ is indeed sufficient, but that doesn't guarantee that it couldn't be shorter still. I suppose the best approach would be to assume a different configuration would take longer, and prove otherwise. Once you have the worst case scenario, you also know the minimum amount of time to clear that area. $\endgroup$
    – Neil
    Jun 30, 2014 at 12:32
  • $\begingroup$ i meant 1 not 2 but that did not include going to C at the end $\endgroup$
    – kaine
    Jun 30, 2014 at 13:37

1 Answer 1

Reset to default
1
$\begingroup$

Although the question is for one answer the comments are slightly confused about the minimum so below are the minimum and maximum times for all robots to exit the square:

Minimum time: √2
If all robots are on the line that joins A to C then the initial robot can travel directly to C in the shortest time/distance. Every other robot would join with the first and also travel directly to C.

Maximum time: 2 + √2
The worst scenario is where there are only three robots at A, B and D.The first robot has to travel to either B or D, then travel diagonally across the square to direct the final robot.

Justification:
The scenario presented in the maximum time represents the configuration where the robots and the exit are all as far away from each other as possible, hence each corner of the square has a robot or the exit. Adding more robots to the play-field cannot increase this maximum distance due to two reasons:

1. Each new robot can travel in a different direction to the first robot which can reduce the overall time needed for all robots to leave the square. For instance if there are four robots and the fifth is at the centre of the square the first robot would travel to the robot at the centre then it could travel to B and then directly to C. This would give a travel time of 1+√2. The robot at the centre would travel to D and then on to C. The travel to B and D happens at the same time and do reduces the overall cost.

2. A mathematician could probably phrase this better so my apologies if it is not concise. If you imagine that there are at least three robots at A, B and D and lets imagine that the robot at A travels to B. From that point the longest distance to D and then C is diagonally across the square which divides the square into two triangles. Now assume that there are no robots in the triangle ABD but there is one somewhere in BCD. In order to increase the maximum length of robot A's journey this distance must be greater than the two legs B->D and D->C but there are no triangles that can fit within BCD with a greater total of side lengths. This means that the greatest distance the robot has to travel is BDC. If this is the case for a journey going from A to C through a triangle at BCD then it would also be true if we travelled in the opposite direction from C to A through triangle ABD.

When there are robots at A, B and D then there is a better chance of achieving 1+√2.

Hope that explains it well enough but the following pictures describe the minimum, maximum and explanation of maximum in, hopefully, a clearer way:
ShortestlongestJustification

Improve this answer
$\endgroup$
7
  • $\begingroup$ Sorry there are two questions but I believe I answered both. $\endgroup$
    – Alan
    Jul 31, 2014 at 16:57
  • $\begingroup$ Well I 100% agree that that is the answer but don't have a good way to prove it. Thank you. $\endgroup$
    – kaine
    Aug 1, 2014 at 12:53
  • $\begingroup$ I'm not entirely Sure - in your last picture you are always assuming, there is a free robot, which can just get the new point without having to go back to D afterwards. But couldn't there be two new targets, so both robots from B have to deviate from the diagonal course? One would then have to go to D and C afterwards, which is longer than the original course... Can you prove there is no such constellation ? $\endgroup$
    – Falco
    Aug 5, 2014 at 11:58
  • 1
    $\begingroup$ Your "proof" doesn't take into account the possibility that certain layouts with robots on B and D would not allow B to be on the path to D. For example, add robot E at the midpoint of AD, and F at the midpoint of BC. If B is visited first, then one robot would have to head straight toward D, and could play no part in waking E and F. Once D was awake, it and the robot that woke it would have to head immediately for C. The shortest sequence of events that would start by having Robot Zero wake B would thus have length ABEFC or ABFEC. $\endgroup$
    – supercat
    Sep 22, 2014 at 20:57
  • 1
    $\begingroup$ Obviously in the indicated scenario, Robot Zero could simply proceed AEDBFC waking every robot it touches (and things could be even faster using paths AEBC and AEDFC) but the fact that one may have to vary the sequence of robot visits would suggest a need to enumerate more cases. $\endgroup$
    – supercat
    Sep 22, 2014 at 21:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.