Train route

The connection vectors $\vec b = \vec{AB}$ and $\vec c = \vec{AC}$ between the city and the villages each have the same length $b = c = 30$ and an angle $\alpha = \angle(\vec b, \vec c) = 40^\circ$ . The idea is to lay a Y-shaped rail track in-between with a turnout in point $P$ . Although this route is not optimal for the train service, the construction costs for the track can be minimized. The connection vector to point $P$ equals $\vec r = \left( \begin{array}{c} r \cos \frac{\alpha}{2} \\ r \sin \frac{\alpha}{2} \end{array} \right)$ The total length of the track results $\begin{aligned} l &= r + |\vec b - \vec r| + |\vec c - \vec r| = r + 2 |\vec b - \vec r| \\ &= r + 2 \sqrt{ (b - r \cos \frac{\alpha}{2})^2 + r^2 \sin^2 \frac{\alpha}{2} } \\ &= r + 2 \sqrt{ b^2 + r^2 - 2 r b \cos \frac{\alpha}{2} } \\ \end{aligned}$ If we plot the function $l(r)$ , we get a minimum at $r \approx 22.3\,\text{km}$ and $l \approx 46\,\text{km}$ .

Because the situation is symmetric, choose the origin at point A and run the $x$ -axis along the angle bisector of $\angle CAB$ . The coordinates of $B,C$ are $(a,\pm b)$ where $a = 30\cos 20^\circ$ and $b = 30\sin 20^\circ$ .

The shortest solution may a involve point $P$ and three pieces of track $AP, BP, CP$ . We don't exclude the possibility that two pieces of track suffice; in that case, we would simply have $P = A$ . Let the coordinates of $P = (x,y)$ . Symmetry suggests $y = 0$ (we can make this more precise later). The amount of rails needed is a function of $x$ , $\ell(x) = x + 2\sqrt{(a - x)^2 + b^2}.$ Minimizing this requires a zero derivative, i.e. $0 = \frac{d\ell}{dx} = 1 - \frac{2(a - x)}{\sqrt{(a - x)^2 + b^2}}.$ Multiply by the denominator, separate, and square to find $(a - x)^2 + b^2 = (2(a-x))^2,$ $3(a - x)^2 = b^2,$ $x = a - \frac{b}{\sqrt 3},$ $\ell = a + \sqrt{3}\:b.$

Substitute $a = 30\cos 20^\circ$ and $b = 30\sin 20^\circ$ to conclude $\ell \approx \boxed{46}$ km.

Note that for this optimal solution, $\angle APB = \angle BPC = \angle CPA = 120^\circ$ .

Since $\triangle ABC$ is an isosceles triangle, the minimum amount of track would form a Y-shape as shown below, where $AD$ bisects $\angle A$ .

The total amount of track would be $T = b + 2a$ , where $a = \frac{30 \sin 20°}{\sin x}$ and $b = \frac{30 \sin (160° - x)}{\sin x}$ according to the law of sines, so $T = \frac{30 \sin (160° - x) + 60 \sin 20°}{\sin x}$ .

The minimum amount of track would be when $T’ = 0$ , or when

$\frac{(\sin x) (30 \cos (160° - x) (-1)) - (30 \sin (160° - x) + 60 \sin 20°) \cos x}{\sin^2 x} = 0$

$-30 \sin x \cos (160° - x) - 30 \sin (160° - x) \cos x - 60 \sin 20° \cos x = 0$

$-30 (\sin x \cos (160° - x) + \sin (160° - x) \cos x) - 60 \sin 20° \cos x = 0$

$-30 \sin (x + 160° - x) - 60 \sin 20° \cos x = 0$

$-30 \sin 160° - 60 \sin 20° \cos x = 0$

$-30 \sin (180° - 20°) - 60 \sin 20° \cos x = 0$

$-30 \sin 20° - 60 \sin 20° \cos x = 0$

$-60 \sin 20° \cos x = 30 \sin 20°$

$\cos x = -\frac{1}{2}$

$x = 120°$

The minimum amount of track is therefore $T = \frac{30 \sin (160° - 120°) + 60 \sin 20°}{\sin 120°} \approx \boxed{46}$ .

The problem is basically asking for a point which has minimum total distance to A B and C. That's the Fermat Point of triangle. Denote it as P. It has three 120° angles when connected to the three vertexes (can be proved geometrically or physically). Triangle BAC being isosceles simplifies the calculation. By Law of Sines, we have sin120/30=sin20/PB=sin40/PA. So PA~=22.3 , PB~=11.8 , and hence total length of railway shall be PA+2PB ~=46 2017.12.27

There exist a point $P$ such that $AP+BP+CP$ achieve it's minimum value. We are finding the minimum value of $AP+BP+CP$ . Rotate triangle $ABC$ and point $P$ with $60°$ degree counterclockwise by centre $A$ . Let the new image is triangle $AB'C'$ and point $P'$ .

Note that $AP=AP'$ and $\angle PAP'=60°$ , so $PP'=AP$ . Besides that, $B'P'=BP$ . Hence, we can conclude that $AP+BP+CP=PP'+B'P'+CP$ . $PP'+B'P'+CP$ achieve its minimum value when $B'C$ is a straight line, or $B'AC$ is a triangle.

Hence, the required length is $\sqrt{30^2+30^2-2\times 30^2 \times \cos(60°+40°)}=45.96$ . Hence, the answer is $\large 46$ .

For people like me who are bad at geometry:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

from math import *

def rad(angleD):
    return angleD*pi/180

def varAndPrint(variable):
    try:
        for k,v in globals().items():
            if(v == variable):
                print(k,v)
    except:
        for k,v in locals().items():
            if(v == variable):
                print(k,v)

# Begin:
'''
Half the length from B to C
'''
bc_half = 30*sin(rad(20))
'''
The altitude of the triangle from A. It's an isoceles triangle so it's gonna be a track
along the altitude plus two symmetric tracks shooting off of this track to B and C.
'''
altA = 30*cos(rad(20))

# The function we want to zero out:
def solveMe(rA, rB):
    try:
        return abs(asin((altA-rA)/rB) - rad(70) + asin(rA * sin(rad(20))/rB))
    except:
        return inf
'''
O(n**2) solution. n being the number of datapoints along the altitude of A.
rA is how long the main track is. We iterate through possible values and minimize rB
rB is length of one of the branch tracks
I made a little optimization on the search space of rB using the triangle inequality
'''
minTracks = 70
rA = 0
while rA < altA:
    rB = bc_half
    bestRB = -1
    minSol = 30
    while rB < altA-rA+bc_half:
        cache = solveMe(rA,rB)
        if cache < minSol:
            minSol = cache
            bestRB = rB
        rB += .05

    cache = rA+bestRB*2
    if cache < minTracks:
        minTracks = cache

    rA += .05

varAndPrint(minTracks)
minTracks = round(minTracks)
varAndPrint(minTracks)

Yields:

1
2

minTracks 45.92120859954035
minTracks 46

Using basic trigonometry, we can find out that our points $A,B,C$ can be placed in coordinate system in the following way:

where $a = 30\sin(20^\circ), b = 30\cos(20^\circ)$ .

The blue lines are rails to be built, so we want to minimize their total length, which corresponds to minimizing the function $f(x,y) = \sqrt{(x - a)^2 + y^2} + \sqrt{(x + a)^2 + y^2} + \sqrt{ x^2 + (y - b)^2}$ .

Now, this would be extremely tedious to minimize by hand. Luckily, such a point $P$ is a known center of a triangle - Fermat point . Following the construction given at Wikipedia, it is obvious that minimum of $f$ occurs when $x= 0$ , so we can simplify the problem to minimizing $g(y) = f(0,y) = 2\sqrt{y^2+a^2}+\sqrt{(y-b)^2}$ . Furthermore, it is obvious that minimum should occur for $y\in [0,b]$ , and thus $g$ simplifies to $h(y) = 2\sqrt{y^2+a^2}+(b-y)$ . Taking derivative gives us $h'(y) = \frac{2y}{\sqrt{y^2+a^2}} - 1$ and solving $h'(y) = 0$ gives us $y = \frac a{\sqrt 3}$ . Thus, the minimum distance is $h(a/\sqrt 3) \approx 45.9627 \approx 46.$

Let $X$ be a set of points, where, for $i\in \{1,2,...,n\}, x_i \in X$ . Let $(x,y)$ be the location of the rail switch. We wish to minimize the total distance $D = \sum d_i = \sum \sqrt{(x-x_i)^2 + (y-y_i)^2}$

For the sake of ease, we minimize the sum of squares of distances, $D_s$ :

$D_s = \sum (x-x_i)^2+(y-y_i)^2$

We differentiate with respect to $x$ :

$\partial_xD_s = 2\sum (x-x_i) = 0$

Solving for $x$ , we see that $x = \frac{1}{n}\sum x_i = \bar{x}$ . Similar analysis shows that $y=\bar{y}$ . Computing these values gives us $(\bar{x},\bar{y})=(17.66,6.428)$ . The total length of track is now simply the sum of the distances from this point to the points $(0,0)$ , $(30,0)$ , and $(30\cos40,30sin40)$ , which yields approximately 46 km.

Note that this can be generlized to higher dimensions for larger sets of points.

By the triangle inequality, and the fact that the shortest distance between any two points is the straight line distance, we can say that the shortest rail will be consumed when a point in the triangle will have minimum sum of distances with the points A, B and C.

Every isolated system tends to acquire a minimum potential energy state.

Now, let us keep the triangle on a table, and poke holes at the points where A, B, and C lie. Now, we take three strings (length quite long), and join one end inside the triangle, and the other coming down from the holes, and we attach a mass $M$ to all three. Leaving them isolated, they rearrange such that the sum of heights of the three masses from ground is minimized, because the gravitational potential energy is $mgh$ .

This point minimizes our rail route, as the length of the strings was the same. Now, at the junction,vector sum of three equal forces is null, which means they are at $120^{\circ}$ to each other.

With this information, we can easily calculate the distances by Sine Rule.