MathDB
Train your abilities of making partial scores

Source: 1st German pre-TST 2005, 6 Dec 2004, Problem 2

December 15, 2004
analytic geometrygeometry unsolvedgeometrySteiner TreesGermanyTSTTeam Selection Test

Problem Statement

Let MM be a set of points in the Cartesian plane, and let (S)\left(S\right) be a set of segments (whose endpoints not necessarily have to belong to MM) such that one can walk from any point of MM to any other point of MM by travelling along segments which are in (S)\left(S\right). Find the smallest total length of the segments of (S)\left(S\right) in the cases
a.) M={(−1,0),(0,0),(1,0),(0,−1),(0,1)}M = \left\{\left(-1,0\right),\left(0,0\right),\left(1,0\right),\left(0,-1\right),\left(0,1\right)\right\}. b.) M={(−1,−1),(−1,0),(−1,1),(0,−1),(0,0),(0,1),(1,−1),(1,0),(1,1)}M = \left\{\left(-1,-1\right),\left(-1,0\right),\left(-1,1\right),\left(0,-1\right),\left(0,0\right),\left(0,1\right),\left(1,-1\right),\left(1,0\right),\left(1,1\right)\right\}.
In other words, find the Steiner trees of the set MM in the above two cases.
Back to ProblemsView on AoPS