2

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.
Community
  • 1
Ali
  • 698
  • 6
  • 12
  • This is very similar to http://puzzling.stackexchange.com/questions/548/fastest-way-to-collect-an-arbitrary-army – Ross Millikan Jun 30 '14 at 00:00
  • 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$ – kaine Jun 30 '14 at 01:51
  • $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... – Ali Jun 30 '14 at 08:54
  • @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. – Neil Jun 30 '14 at 12:32
  • i meant 1 not 2 but that did not include going to C at the end – kaine Jun 30 '14 at 13:37
  • @Neil I think this is the worst case scenario - When you have one robot at each of A, B and C, so it's $AB + BD + DC = 2 + \sqrt{2}$. So, now to assume a different configuration would take longer than this and prove otherwise... It sounds like a good place to start from, thank you. – Ali Jun 30 '14 at 13:39
  • @kaine, do you agree though that it is $2 +\sqrt{2}$ if you do go to C at the end? – Ali Jun 30 '14 at 13:41
  • Yes that is the obvious lower bound for this question just as it was for the other one. There could be an arrangment that requires more, however, and the problem with both questions is proving there isnt one. – kaine Jun 30 '14 at 14:25
  • Would it be helpful to rephrase the question to say that all robots can communicate with each other instantaneously, but all robots other than Robot Zero are powered down, and may only be activated by contact with a live robot? – supercat Sep 22 '14 at 20:03

1 Answers1

1

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

Alan
  • 316
  • 1
  • 4
  • Sorry there are two questions but I believe I answered both. – Alan Jul 31 '14 at 16:57
  • Well I 100% agree that that is the answer but don't have a good way to prove it. Thank you. – kaine Aug 01 '14 at 12:53
  • 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 ? – Falco Aug 05 '14 at 11:58
  • Sorry the last picture was to illustrate that any free robot could be collected and returned to C by the robot collected at B before the initial robot collects the robot at D and returns to C. In fact I suspect that the more free robots there are the higher chance of achieving a time of 1+√2 rather than the maximum time of 2+√2. So in essence the last picture was to demonstrate that there is no placement of a free robot in the triangle BCD that results in a longer time than traversing the triangle BCD. Hope that clarifies. – Alan Aug 05 '14 at 14:55
  • I'm convinced that this is a local max of sorts, but not that it's an absolute max. That is, adding any one robot will not make it worse, but it's not evident that adding another robot after that won't make it worse than the first. Do you have a way to show that adding more robots won't end up giving the existing robots too much to do? – TheRubberDuck Sep 02 '14 at 20:26
  • 1
    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. – supercat Sep 22 '14 at 20:57
  • 1
    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. – supercat Sep 22 '14 at 21:01