9
$\begingroup$

On the $\mathbb{R}^2$ plane, the devil has trapped the angel in an equilateral triangle of firewalls.

enter image description here

The devil

  • starts at the apex of the triangle.
  • 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$.


Question 1: how should the devil move to catch the angel in the shortest amount of time?

Question 2: if the devil is given a fixed length of firewalls to enclose the angel in the beginning, what shape maximizes the survival time of the angel? (The devil always starts on the firewall)

$\endgroup$
8
  • $\begingroup$ Is the side length 1? $\endgroup$ Commented Sep 7, 2021 at 13:52
  • $\begingroup$ This seems to be equivalent to the problem: Say the catch time of a shape is the minimum over curves bisecting the shape of the length of the curve plus the maximum of the catch times of the two remaining halves. What is the catch time of the triangle? What is the largest catch time of any shape with a given perimeter length? $\endgroup$
    – Will Sawin
    Commented Sep 7, 2021 at 14:08
  • $\begingroup$ If I think correctly, then the devil should divide the initial shape into halves. The angel must eventually decide to stay in one half, and the devil continuous by subdividing this part, and so on. Now, the goal of the devil is to choose a subdivision that uses the shortest possible dividing lines. The angel can always decide to teleport to the half where the devil needs longer dividing lines. So the devil should ensure that the two emerging halves are equally good in this respect. For a square of side length one the chase should be over in time 2, but it is more complicated for the triangle. $\endgroup$
    – M. Winter
    Commented Sep 7, 2021 at 14:11
  • $\begingroup$ @M.Winter Time 2 is probably not feasible for your square. $\endgroup$
    – Eric
    Commented Sep 7, 2021 at 14:14
  • 2
    $\begingroup$ @M.Winter Yes, but I'm not sure if that's a shortest time plan for the square. $\endgroup$
    – Eric
    Commented Sep 7, 2021 at 14:18

3 Answers 3

5
$\begingroup$

Here is another attempt to improve the upper bound. Let $y$ be the shortest time required to catch the angel in the equilateral triangle of side length 1. The devil may cut the triangle horizontally along a chord of length $a = (56+15\sqrt{3}-\sqrt{1143+852\sqrt{3}})/46\approx0.669727$. The angel is force into either a smaller equilateral triangle, requiring the devil to use $ay$ time to catch her, or into the trapezoid, which is contained in a $1\times(1-a)(\sqrt{3}/2)$ rectangle. If the angel is in the trapezoid, she will be caught in at most $3(1-a)(\sqrt{3}/2)+1/2$ units of time (similar argument to Will Swain's comment to his answer, but in this case the long side is between 2 and 4 times the short side). Let $y_0 = 3(1-a)(\sqrt{3}/2)+1/2 + a = (1+\sqrt{9+24\sqrt{3}})/4 \approx 2.0278$. Note that $a$ was chosen such that we also have $y_0 = a + a y_0$. So we now have that $y\le \max(y_0, a+a y)$. Put otherwise, $y\le y_0$ or $y\le a + a y$, but the latter inequality simplifies to the former and we simply have $y\le y_0\approx 2.0278$.

$\endgroup$
1
  • $\begingroup$ For question 2, if it's true that for a square of side length 1 the minimum catch time is 3, then this answer supports the intuition that for fixed circumference, the "rounder" shape will cost the devil more time. $\endgroup$
    – Eric
    Commented Sep 8, 2021 at 14:16
3
$\begingroup$

Here is an upper bound for the triangle of side length $1$.

First, divide in half into two triangles of angles $\frac{\pi}{6},\frac{\pi}{3}, \frac{\pi}{2}$ triangle and side lengths $1, \frac{\sqrt{3}}{2},\frac{1}{2}$. This requires drawing an edge of length $\frac{\sqrt{3}}{2}$. It doesn't matter which one the angel goes into.

Next, divide each of these triangles into two triangles with angles $\frac{\pi}{6},\frac{\pi}{3}, \frac{\pi}{2}$. The angle wisely goes into the larger one. Repeat this process.

Starting from a triangle with side lengths $a, \frac{\sqrt{3}}{2} a, \frac{1}{2}a$, this produces a triangle of side lengths $\frac{\sqrt{3}}{2} a, \frac{3}{4}a, \frac{\sqrt{3}}{4}a$, after drawing an edge of length $\frac{\sqrt{3}}{4}a$.

So the total length drawn is

$$ \frac{\sqrt{3}}{2} + \frac{ \sqrt{3}}{4} + \frac{ \sqrt{3}}{2} \frac{ \sqrt{3}}{4} +\left( \frac{ \sqrt{3}}{2}\right)^2 \frac{ \sqrt{3}}{4} + \dots = \frac{\sqrt{3}}{2} + \frac{ \frac{\sqrt{3}}{4}}{1- \frac{\sqrt{3}}{2}}= \frac{\sqrt{3}}{2} + \frac{ \sqrt{3} }{4 - 2 \sqrt{3} }=\frac{3 \sqrt{3} -3}{4 - 2 \sqrt{3}} =4.098\dots$$

which is probably not optimal.

$\endgroup$
4
  • 1
    $\begingroup$ A simple observation is that if you can cover figure A with figure B, then catch time $T_A\leq T_B$. Since you can cover the triangle with a square and $T_{square}\leq 3$ as suggested in the comment, we must have $T_{triangle}\leq 3$. $\endgroup$
    – Eric
    Commented Sep 7, 2021 at 15:23
  • 2
    $\begingroup$ @Eric An $a \times b$ rectangle with $2b \geq a \geq b$ can be done in time $b + \frac{a}{2} + \frac{b}{2} + \frac{a}{4} + \dots = 2b + a$, so since the triangle fits in a $1 \times \sqrt{3}{2}$ rectangle, it can be done in time $1 + \sqrt{3} < 3$. $\endgroup$
    – Will Sawin
    Commented Sep 7, 2021 at 15:28
  • $\begingroup$ I had an idea to refine the above approach by splitting the $\frac{\pi}{6}, \frac{\pi}{3}, \frac{\pi}{2}$ triangle into an equilateral triangle and a $\frac{\pi}{6}, \frac{\pi/6}, \frac{2\pi}{3}$, which seems more even and thus more optimal, but I don't know if it will beat the rectangle approach. $\endgroup$
    – Will Sawin
    Commented Sep 7, 2021 at 15:34
  • $\begingroup$ @WillSawin Sorry, I realized this and deleted my comment already. $\endgroup$
    – M. Winter
    Commented Sep 7, 2021 at 15:45
3
$\begingroup$

It seems there is value to think about about splitting the triangle into 3 or 4 pieces rather than just 2 in each stage. I give a natural approach that achieves 3, and another which gives $\frac{1}{3} +\sqrt{3}\le 2.06539$.

For any two points $x,y$, let $xy$ denote the line segment from $x$ to $y$.

For example, one natural approach is to try and split the triangle into 4 equilateral triangles. Let $a,b,c$ be the points of our triangle. We start by teleporting to the midpoint of $ab$. Then, we move from the midpoint of $ab$ to the midpoint of $bc$, and then to the midpoint of $ca$. This takes length 3/2. In doing so, we have scaled the triangle down by a factor of 1/2. We may now repeat, this time able to teleport to a midpoint, now only requiring length 3/4, and so on.

Hence, this gives an upper bound of $3\sum_{i=1}^\infty 2^{-i} = 3$, as desired.

Now, what if we split the triangle into three parts? Let $d,e,f$ denote the respective midpoints of $ab,bc,ca$. Let $o$ be the interesection of $dc$ and $ea$. We walk from $d$ to $o$, $e$ to $o$ and $f$ to $o$. Each segment has length $\frac{1}{2\sqrt{3}}$, thus this in total costs $\sqrt{3}/2\le 0.86603$.

The angel will be trapped in a quadrilateral $Q$, since our triangle is split into 3 identical copies. WLOG, we assume the vertices of $Q$ are $a,d,f,o$. We have that $Q$ is contained in a equilateral triangle $T$ of height $1/\sqrt{3}$ (indeed, consider the line $\ell$ parallel to $df$ through $o$, we have that $Q$ is contained in the triangle whose vertices are $a$ and the intersection of $\ell$ with our initial triangle). We have that said triangle has side lengths 2/3.

Now, suppose we try to iterate, and split our triangle $T$ into 3 parts. We first draw the line parallel to $do$, then the line parallel to $fo$. The angel has two choices. Either, it goes in the new quadrilateral $Q'$ that is formed, or it is on the other side. In the first case, it is easy to see that $Q'$ is similar to $Q$, and 2/3 as large (since $T$ is 2/3 as large as our initial triangle). In the other case, we add the third line (which will be will be in the same direction as $oe$); here the angel is stuck in one of two parts which are each covered by a copy of the $1/6\times \frac{1}{2\sqrt{3}}$ rectangle.

We now can analyze the total length required to catch the angel once it is in $Q$. Let $L$ denote the total length needed if we follow the above strategy, (namely adding two lines, then scaling down if the angel stays in $Q'$, or adding the third line and doing a rectangle strategy otherwise), assuming the angel behaves optimally.

If the angel chooses to stay in $Q$, then we only added two edges each of length $(2/3) \frac{1}{2\sqrt{3}}$, for a total length of $\frac{2}{3\sqrt{3}}$, and since $Q'$ is a 2/3 scaled down copy of $Q$, we will catch the angel having used length $\frac{2}{3}L+\frac{2}{3\sqrt{3}}$ here.

In the other case, we add 3 lines, whose net length is $\frac{1}{\sqrt{3}}$. By the argument given by Sawin's comment below his answer, we can do the rectangle using length $2(1/6)+(1/2\sqrt{3})$. This totals to a length of $\frac{1}{3}+\frac{\sqrt{3}}{2}\le 1.19936$.

Hence, we just solve for $L = \max\{\frac{1}{3}+\frac{\sqrt{3}}{2},\frac{2}{3}L+\frac{2}{3\sqrt{3}}\}$. Observing the solution to $x= (2/3)x +\frac{2}{3\sqrt{3}}$ is $2/\sqrt{3} \approx 1.15470$, we see that $L =\frac{1}{3}+\frac{\sqrt{3}}{2}\le 1.19936$. It follows that we can catch the angel in our triangle by adding our initial cost $\frac{\sqrt{3}}{2}$ to $L$, which gives $1/3 + \sqrt{3} \le 2.06539$.

Perhaps we get get a slightly better solution by optimizing the second case, since they are not truly rectangles.

$\endgroup$
3
  • $\begingroup$ Am I confused? By my reckoning, the smaller equilateral triangle has height $\frac1{\sqrt3}-\Delta$, hence edge length $\frac2{\sqrt3}(\frac1{\sqrt3}-\Delta)$ rather than $\sqrt3/4-\Delta$. $\endgroup$ Commented Sep 8, 2021 at 15:32
  • $\begingroup$ oops, yes, you are correct. I will correct my work, hopefully this does not ruin the bound. $\endgroup$ Commented Sep 8, 2021 at 15:38
  • $\begingroup$ a way to optimize this would be to have the split of Q be slightly off center, making Q' a little larger so that rectangle case is a little better $\endgroup$ Commented Sep 8, 2021 at 17:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .