19
$\begingroup$

On an infinite plane, the Prime Star has disintegrated into four constituent stars, the North Star, the South Star, the East Star and the West Star, each traveling at a constant speed of 1 in their eponymous directions.

enter image description here

The Star Guardian at the center wants to reunite the four Stars back into the Prime Star again, which can only be achieved if the four Stars meet at a single point in spacetime. Furthermore:

  1. The Star Guardian moves at a constant speed of $g$, in any direction she wants.
  2. She is only able to take one Star with her in her movement.
  3. Once left alone, the four Stars always travel in their eponymous directions at speed 1.
  4. If only two or three Stars meet, they will just pass through each other without any interaction.

Suppose now 1 unit of time has passed so each Star is at distance 1 from the Guardian, what is the minimum value of $g$ for her to be able to reunite the Stars in finite time? How long will it take her in that mission?


Update: it is possible that there exists $g^*$, such that the Guardian is able to complete her mission for any $g\gt g^*$, but not for $g\leq g^*$. If this is the case, identify this $g^*$.

$\endgroup$
18
  • 5
    $\begingroup$ What's the air speed velocity of a laden Star Guardian? $\endgroup$ Aug 17, 2021 at 15:03
  • 2
    $\begingroup$ @ChrisCudmore Always g, laden or not. $\endgroup$
    – Eric
    Aug 17, 2021 at 15:05
  • 6
    $\begingroup$ @ChrisCudmore What do you mean? An African or European Star Guardian? $\endgroup$
    – hexomino
    Aug 17, 2021 at 15:33
  • 1
    $\begingroup$ Yes, though in the limitng cycle only N/S and E/W are aligned in time. Say the guardian catches N at 1 unit out tows it over to S a bit farther out drops it while collecting S and returns to its starting point total effect being N and S exactly swapped. Then goes diagonally to E catching it also at one unit out and swaps E and W then goes diagonally back to N. $\endgroup$
    – loopy walt
    Aug 18, 2021 at 5:20
  • 1
    $\begingroup$ My mathematical intuition (rather than a formal proof) suggests that for pretty much any geometry of the collecting pattern, the minimum g would be a limit as the geometry expands towards infinity - informally, if there were a hard minimum with a bounded pattern, it would imply that collecting the stars in a slightly expanded version of the pattern (with the stars having moved further and thus taking more time) would require the guardian to move faster, but with more time to collect the stars, the guardian can move a tiny bit slower and still catch each star before it reaches the boundary. $\endgroup$
    – Steve
    Aug 18, 2021 at 6:37

3 Answers 3

11
$\begingroup$

UPDATED WITH A COMPLETE REWRITE

A minimum velocity does

not exist.

First observe the hard lower bound

g > 3

This is straightforward to establish:

Consider the velocity vectors of the freely moving star. These are constant unit vectors representing the four principal winds. Now take scalar product of each with the corresponding star's position vector. For each star that is not in the immediate care of the guardian this product will grow at a rate of 1. Now consider the sum of these scalar products. When all stars meet its value is zero. In the initial configuration it is four, so to make the stars meet it must be shrunk. As at each time at least three stars contribute growth at rate 1 each the guardian can not compensate unless its speed is strictly above 3.

I will now show simulations of a strategy that strongly suggest that

any g > 3 is actually good enough:

The strategy has to phases:

Phase 1:

Cycle through the stars E->N->W->S->E->... always using the quickest intercept course to reach the next and always carry the just intercepted star all the way to the next (so we never travel empty).

enter image description here
This is a simulation with g about 1% above 3. Values much closer to 3 give qualitatively the same picture.

Panel 1: At first the configuration appears to expand rather quickly. Panel 2: But a spiralling pattern is quickly establishied with the rate of expansion shrinking over time ... Panel 3: ... until it is actually reversed resulting in a collapsing spiral. Panel 4: This, however, is reversed again at some point leading to renewd growth. Panels 5 and 6: The trend keeps reversing resulting in perpetual oscillation.

Phase 2:

The second part of the strategy breaks this yoyo behaviour the instant the system first goes into shrinkage by tempering its rate. More precisely, as soon as the guardians steps are detected to reduce the lateral (wrt its current cargo's free velocity vector) displacement we reduce the reduction by 50% (smaller values resulting in faster convergence are also possible,see below for an example). In simulations this reliably prevented the next reversal.

enter image description here

enter image description here
The last curve summarised the continual reduction of the configuration's diameter many orders of magnitude below its inital value in finite time.

Few more examples with

g < 3.001
enter image description here

and the same with reduced shrinkage reduction (6% instead of 50%).
enter image description here

g < 3.0003 ; shrinkage reduction < 1%
enter image description here

g < 3.00003 ; shrinkage reduction < 1‰
enter image description here

$\endgroup$
39
  • 1
    $\begingroup$ Also I get it now about your strategy. Basically we consider the value $V$ to be the sum of speed of the stars moving away from our designated rendezvous point. Since we can carry 1, maximum $V$ is at least 3, so g should at least be 3 as well to "counter" this effect. $\endgroup$
    – justhalf
    Aug 19, 2021 at 5:43
  • 1
    $\begingroup$ @loopywalt, do you have analytical solution for the 10/3? $\endgroup$
    – justhalf
    Aug 19, 2021 at 9:46
  • 1
    $\begingroup$ @Eric yes, that is actually easy to see in both scenarios. We have the lower bound g > 2m-1 (take sum of the dot products of the stars' positions and velocity vectors with no guardian this will increase at a rate of 2m with guardian at a rate >= 2m-1 - g) for an upper bound 4m + epsilon will allow you to go for one star after the other and bring it back to the origin. over time the individual distances will equilibrate and shrink. $\endgroup$
    – loopy walt
    Aug 21, 2021 at 12:09
  • 2
    $\begingroup$ @Eric have you been reading my mind again? I'm in the middle of updating my answer with exactly that. $\endgroup$
    – loopy walt
    Aug 25, 2021 at 6:44
  • 2
    $\begingroup$ "we reduce the reduction by 50%" what do you mean by this? Surely it's not about reducing the speed of the guardian. But what? $\endgroup$
    – justhalf
    Aug 25, 2021 at 7:47
6
$\begingroup$

I have a strategy with infimum $g^* = \frac{1}{2}\left(4+\sqrt{2}+\sqrt{22+4\sqrt{2}}\right) \approx 5.336596$, and any larger value is a solution. For example, $g = 5.3366$ is doable (with the corresponding $X \approx 117058$).
$g* = 5.31317$ is feasable when not ending in the origin (I uses a MP solver for this)

The strategy:

move to/ pick up weststar
move far to the east distance $(g+1)X$ and release west
move to the west, pick up eaststar on the way and drop it at $(g-1)X$ west
note: east and west will reach origin at the same time

move southeast and pick up southstar
note: at this $g$ you will meet the star at $(g-1)X$ to the south of the origin
move to $(g+1)X$ north to get the north star; drop southstar at the right moment on the way (precisely at $\frac{X(g-1)(g-1-\sqrt{2})}{g+1}$, which we can confirm is less than $(g+1)X$)
move northstar to the origin

note all stars reach the origin at the same time
weststar is dropped at $(g+1)X$ east at time $\frac{X(g+1)}{g}$
eaststar is dropped at $(g-1)X$ west at time $\frac{X(3g+1)}{g}$
southstar is picked up at $(g-1)X$ south at time $\frac{X(3g+1)}{g} + \frac{X(g-1)\sqrt{2}}{g}$
and this works since for $g^*$ specified above, we have: $(g-1)X = \frac{X(3g+1)}{g} + \frac{X(g-1)\sqrt{2}}{g}$
northstar is picked up at $(g+1)X$ north at time $(g-1)X +2X$
all are together at time $\frac{X(g+1)^2}{g}$
enter image description here Notes:
This assumes there is no initial distance, but the calculation still works, i.e., the same $g^*$ would be the solution with the initial distance in (just need to add $\frac{2}{g-1}$ to the time to get to the southstar. Note that this doesn't affect the rest of the calculation due to how we pick the distances).

The solution is not optimal; With a similar strategy, one can do slightly better while ending up south-west of the origin.
EDIT: The direction is an error on my part. I expected the configuration below to be more efficient. I reasoned the angle at a is sharper than at c and thus moving the end position towards c would help. (I tried it using a solver but there is only an adverse effect.)

enter image description here
However, changing the endpoint to (1,-1) gives an improvement
According to my solver $g* = 5.31317$
For $A = 11.456, B = 3.649, C = 6.132$ enter image description here

$\endgroup$
10
  • $\begingroup$ Nice strategy! Given that you provide a number with such precision, perhaps you can try to calculate the actual value given the initial distance of the four stars? $\endgroup$
    – justhalf
    Aug 19, 2021 at 1:44
  • $\begingroup$ Your total time of $X(g+1)/(g-1)$ is not correct, as it is clearly less than $X(g+1)$, the time at which North Star is picked up. It should be $X(g+1) + X(g+1)/g$ or $X(g+1)^2/g$ $\endgroup$ Aug 19, 2021 at 2:38
  • $\begingroup$ @justhalf $X\approx185435$ $\endgroup$ Aug 19, 2021 at 2:40
  • $\begingroup$ I tried calculating this to include the initial distance, and this doesn't work, as X would be negative (due to the requirement that g needs to be large enough, to catch up to north star in time to get back to origin at the same time with other three stars) $\endgroup$
    – justhalf
    Aug 19, 2021 at 3:42
  • 1
    $\begingroup$ Thanks for the help. @justhalf see my additions for the 'not at origin' solution $\endgroup$
    – Retudin
    Aug 19, 2021 at 8:17
0
$\begingroup$

$g=4$ is enough.

First, notice that the initial distance btw the guardian and the stars (i.e. the scale) doesn't matter. A collecting pattern at scale $1$ accomplishes the mission in time $t$ if and only if the same collecting pattern at scale $x$ accomplishes the mission in time $xt$. With this in mind, let's start with each star at distance $1$ from the origin and the guardian at the northstar, and follow the instructions below:

  1. Carry N southward. Drop N upon meeting S and carry S northward to point (0, 1). This step takes $t_0=1.33$ time. At the end the four stars are at N(0, -1), S(0, 1), W(-2.33, 0), E(2.33, 0) and the guardian is at S.
  2. Drop S and head straight for the point (-1.86, 0) to meet W, which takes $t_1=0.53$ time.
  3. Carry W eastward to the point (0, 3.1) to meet E, dropping W somewhere en route at point $W_d$ (to be determined). This step takes $t_2=1.24$ time.
  4. Carry E westward for a time $t_3=0.96$ to the point (-0.74, 0). $W_d$ in step 3 is chosen so that at the end of $t_3$, W is at the point (0.74, 0).

At the end of step 4, $t_1+t_2+t_3=2.73$ time has passed since S is dropped. So now the four stars are at N(0, 1.73), S(0, -1.73), E(-0.74, 0) W(0.74, 0) and the guardian is at E. Notice this is exactly the situation at the end of step 1, only shrinked by a factor of 0.74! By repeating the above cycle, the guardian can converge the four stars in $1.33+\frac{2.73}{1-0.74}=11.83$ units of time.

$\endgroup$
8
  • $\begingroup$ But the position of the guardian at the end of step 1 and step 4 seem to be different? Ah, noted, it's also rotated. $\endgroup$
    – justhalf
    Aug 19, 2021 at 9:41
  • $\begingroup$ The final time needs to include the additional time taken to reach your starting position, and then re-scaled to the scale of the position as it stands at that point. i.e. your real final time is $(1 + 4 * 11.83)/3 \approx 16.11$ $\endgroup$
    – Steve
    Aug 19, 2021 at 11:22
  • $\begingroup$ @Steve I assumed a different starting point for the guardian in the 2nd paragraph. $\endgroup$
    – Eric
    Aug 19, 2021 at 11:42
  • $\begingroup$ Indeed, reaching your assumed starting point from the actual starting point takes 1/3 time units, and scales the whole problem by a factor of 4/3 $\endgroup$
    – Steve
    Aug 19, 2021 at 12:11
  • 1
    $\begingroup$ The technique seems to me broadly similar to the one in @loopywalt's answer which works for significantly lower values of g, so g=4 definitely possible with an equivalent iterative technique, although perhaps not with such an elegant pattern. $\endgroup$
    – Steve
    Aug 19, 2021 at 13:12

Your Answer

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

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