4
$\begingroup$

The devil has trapped the angel in a regular hexagram of firewalls. The perimeter of the hexagram is 12.

enter image description here

The devil

  • starts at the apex of the hexagram.
  • can move at speed $1$ to leave a trajectory of firewall behind, as this

enter image description here

  • can teleport from one point to another along the firewall.

The angel

  • can teleport to any point that is not completely separated by firewalls from her current position.

The devil catches the angel if their distance is $0$.

Find a plan for the devil to catch the angel in less than 7 units of time. The less time your plan takes, the better.

$\endgroup$
7
  • $\begingroup$ Is this turn-based or continuous? If continuous (and if the fire walls are 1 dimensional) then the angel can always escape. So I assume it's turn-based? $\endgroup$
    – Dr Xorile
    Sep 9 at 15:05
  • $\begingroup$ On the other hand, if it's turn-based, the devil can catch the angel is 1 second, since every point is within 1 unit of the outer firewall $\endgroup$
    – Dr Xorile
    Sep 9 at 15:07
  • $\begingroup$ @DrXorile It's continuous. Fire walls are 1 dimensional curves, the angel and the devil are both points. $\endgroup$
    – Eric
    Sep 9 at 15:13
  • $\begingroup$ I do note that there's something a little off about a devil creating a star of david in order to catch an angel. Might be better if you shuffled the characters a touch. $\endgroup$
    – Ben Barden
    Sep 9 at 16:47
  • 3
    $\begingroup$ Ben, I think that the Jewish symbol is always specifically the version that includes the "inner" lines (so it's two intersecting equilateral triangles). Unless there's some sign of malicious intent, which I don't think there is, this doesn't seem worrying to me. But I'm not Jewish, and for obvious reasons some who are might be more sensitive to this sort of thing than I am currently guessing. So if it turns out that someone Jewish reading this was actually upset by it, then I will immediately retract everything I just said and recommend editing the puzzle. $\endgroup$
    – Gareth McCaughan
    Sep 9 at 18:19
4
$\begingroup$

Suboptimal solution: 6.781

The optimal solution seems very complicated.
One should use repeated bisections.
enter image description here The first bisection is obvious, symmetry suggest connecting opposing inner corners. The second bisection is should use one of the inner corners, and somehow divide the half star in two parts that take equal time to finish. It should not be a single straight line; since the remaining inner corner is attractive to use, it should 'bend optimally' where the third bisection (separating A and B in the picture) connects. The optimal solution of the first 3 bisections may look close to the left picture
enter image description here However if we look at bisection 4 in area A and B, line 4a will probably connect to 3a, while 4b will not, bending 3a will have quadratic cost while saving linearly for area A, so bending a (very) little will be beneficial - if the other lines are shifted to spread the benefit to the other areas.
This effect can be extended to later bisections; meaning lines 2,3a,3b and further all probably will have an infinite number of bends in the optimal solution.

enter image description here The second right picture shows a far from optimal solution: 2+sqrt(3) time can be used to trisect the area and contain the angel within an area within a 1.5 by sqrt(3)/2 box, repeatedly halving the box on the long side will cost an additional sqrt(3) +1.5 time. Total: 6.964

enter image description here The left most does one optimization: First bisecting C from A+B allows B to be bigger; I used the same directions, and made the time for A and C the same. Again , further steps (sub optimally) just half a bounding rectangle to get to the mentioned result; e.g. PQRS for region A enter image description here

$\endgroup$
6
  • $\begingroup$ That's really good! May I suggest that you post the four pictures separately in finer resolution to be seen more clearly? $\endgroup$
    – Eric
    Sep 10 at 15:53
  • $\begingroup$ Not sure if this helps much, but at least they are easier to see now without the need to click on them for enlargement.. $\endgroup$
    – Retudin
    Sep 10 at 16:22
  • $\begingroup$ Where exactly do you cut to divide regions "C" and "D"? From your diagram, region "D" looks like the left edge has a length greater than 1.25/2, but your final result seems to depend on both C and D having bounding boxes of sides 1.25/2 and sqrt(3)/2. $\endgroup$
    – JS1
    Sep 10 at 20:15
  • $\begingroup$ The first half is a reasoning of how to get to an optimal solution. I did indeed not explain where the split 3b between C and D is. 3b is just a rough estimate, and it will not be a single strait line according to my reasoning. Only starting at picture 3 I used the bounding rectangle approach to get to a 'simple' upper bound solution below 7. The C,D equivalents in picture 4 uses a bounding box of 1.75/2 and sqrt(3)/2 (and there 3b will be the orthogonal line of length sqrt(3)/2) $\endgroup$
    – Retudin
    Sep 10 at 20:48
  • $\begingroup$ OK I see it now. Your pictures were so small I couldn't read them properly. The bottom pentagon is labeled 1.75 + sqrt(3) and I thought it was labeled 1.25 + sqrt(3). I see now that the bottom pentagon is bounded by 1.75 at the longest point, which makes the left edge of "D" be 0.875 which looks about right according to the diagram. One thing I didn't get before is that if the angel hides in the bottom area, you don't have to bisect A/B. Therefore, the C/D area should be bigger than the A/B area because you "save" 0.5 by not needing to bisect A/B. $\endgroup$
    – JS1
    Sep 10 at 21:03
3
$\begingroup$

There's a solution:

enter image description here

Just pretend the green area is a rectangle with the length of 3/4 units, then repeatedly divide it into two "identical" parts using the smaller dimension unused in the last step.

The devil can trap the angel in some of the regions bordered by the lines (red first, maroon second, green third), teleport to the same side as the angel if needed and eventually rob the angel of any space to move.

$\endgroup$
4
  • 2
    $\begingroup$ This is just like that old Win95 game of capturing bouncy balls by slicing off the area the balls can be in, haha. $\endgroup$
    – justhalf
    Sep 10 at 3:29
  • 2
    $\begingroup$ Since the devil catches the angel only if their distance is 0, this plan takes him exactly 7 units of time. $\endgroup$
    – Eric
    Sep 10 at 3:35
  • $\begingroup$ Here's a better answer. $\endgroup$
    – Nautilus
    Sep 10 at 8:44
  • $\begingroup$ Sorry, this one should be fine. $\endgroup$
    – Nautilus
    Sep 10 at 19:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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