Competition problem — Geometry — Maths Olympiad Prep

Library / /57 of 62

Geometry Difficulty 7.3 National Olympiad, round 2 Prove it Ukraine

The country Plato has the shape of a convex polygon in vertices of which there are border towers. Trucker needs to drive through all towers, and for every kilometre he is ought to pay one puylyk (state currency) to swindlers from the government (route does not have to be closed, the only condition is to visit each tower, and one can go in any direction without going beyond the state border). The perimeter of the state is 3000 kilometres and diameter is 1000 kilometres. Which guaranteed amount of puylyks will the trucker pay to swindlers?

The diameter of a polygon is the largest distance between any pair of vertices.

Solution

If the state has the shape of an equilateral triangle, then obviously, trucker can do the job and pay only 2000 puylyks (in this case the route of the trucker lies along the two sides of the triangle).

Now let us prove that in any case the trucker will have to pay at least 2000 puylyks. Suppose that there is a state that has a shape of a convex $n$ -gon for which trucker manages to do the job paying less than 2000 puylyks. Consider his shortest way. Let us close it (i.e. draw a segment from the starting point to the ending one). The length of the new route

Fig. 44

will increase by not less than 1000 km, so it would be less than the perimeter. Let us prove that this is impossible.

The proof will be based on a few simple statements.

Statement 1. Any part of the way between the two points should be a segment.
If this is not the segment, then by connecting them with the segment we get a shorter route, which is impossible according to our choosing of the shortest closed route.

Fig. 45

Statement 2. All turns on the route must be the vertices of the boundaries of the polygon.
If there is a turn in the point $A$ that is not the vertex on the border, then we have two segments $CA$ and $AB$ included in the route. If we replace them with the segment $CB$ , the route will shorten.

Statement 3. The route can not cross itself.
If the route $AB...X...CD...Y...A$ contains two segments $AB$ and $CD$ that intersect in some point $O$ , then we will consider the route $AC...X...BD...Y...A$ instead. They differ only in pairs of segments $AB$ , $CD$ and $AC$ , $BD$ . Since (fig. 44)
$AB + CD = AO + OB + CO + OD > AC + BD,$
the length of the route decreases. Since the number of all different routes is finite, such decrease in length will end when the route will have no intersections with itself.

From these statements it follows that the route runs along the perimeter, because if somewhere not consecutive vertices are connected with the segment $AB$ (fig. 45), it is no longer possible to connect the vertices $C$ and $D$ without intersections with the route. Thus, the shortest route must be the perimeter, and this contradiction with the assumption completes the proof.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.