tourist wants to visit each of 10 cities shown on picture
Source: ITAMO 1997 p6
January 25, 2020
combinatorics
Problem Statement
A tourist wants to visit each of the ten cities shown on the picture. The continuous segments on the picture denote railway lines, whereas the dashed segments denote air lines. A railway line costs lires, and an air line costs lires. What is the minimum possible price of a desired route?[asy]
unitsize(2.5 cm);real r = 0.05;pair A, B, C, D, E, F, G, H, I, J;A = (0,0);
B = dir(30);
D = dir(-30);
C = B + D;
E = (A + B)/2;
F = (B + C)/2;
G = (C + D)/2;
H = (D + A)/2;
I = (A + B + D)/3;
J = (B + C + D)/3;draw(A--B--C--D--cycle);
draw(E--I--H);
draw(F--J--G);
draw(B--D, dashed);
draw(E--H, dashed);
draw(F--G, dashed);
draw(I--J, dashed);
filldraw(Circle(A,r),white);
filldraw(Circle(B,r),white);
filldraw(Circle(C,r),white);
filldraw(Circle(D,r),white);
filldraw(Circle(E,r),white);
filldraw(Circle(F,r),white);
filldraw(Circle(G,r),white);
filldraw(Circle(H,r),white);
filldraw(Circle(I,r),white);
filldraw(Circle(J,r),white);label("", A + r*dir(225), SW);
[/asy]