6
$\begingroup$

The following problem appeared in a Leningrad Mathematical Olympiad:

The map of a subway system is a convex polygon in which no three diagonals are concurrent. There is a station at each vertex and at every intersection of two diagonals. Train runs along entire diagonals, but not necessarily every diagonal. If each station lies on the route of at least one train, prove that it is possible to go from any station to any other station, changing trains at most twice.

However if the map of the subway system is as follows, I can’t see how to go from station A to station B, changing trains at most twice.

Subway system - 12-sided polygon

My question is: Have I misunderstood the Olympiad question?

I want to try to solve this Olympiad problem once I properly understand it. So please don’t give hints/solution to this Olympiad problem. Thank you.

$\endgroup$
12
  • 4
    $\begingroup$ There is a station at every intersection of two diagonals. (This is not limited to the diagonals that trains run on.) Your map is missing many of these stations. $\endgroup$ Jan 23 at 5:35
  • $\begingroup$ @DanielMathias In my diagram, I only drew diagonals that trains run along. I can see how there would be more stations that I didn’t draw and that would allow a passenger to have more transfer choices. But the passenger is still limited to the train routes I have drawn. $\endgroup$ Jan 23 at 5:53
  • 4
    $\begingroup$ "Each station lies on the route of at least one train." The routes you have drawn do not service all stations. As such, your map is not valid for the question. $\endgroup$ Jan 23 at 5:58
  • 3
    $\begingroup$ You have to consider all diagonals. All their pairwise intersections are stations and each station must be serviced meaning that of every pair of diagonals that do intersect (inside the polygon) at least one must be active. $\endgroup$
    – loopy walt
    Jan 23 at 7:00
  • $\begingroup$ @DanielMathias Thank you for helping me understand the question. $\endgroup$ Jan 23 at 7:08

1 Answer 1

4
$\begingroup$

Via comments, three users (Daniel Mathias, loopy walt and hexomino) helped me properly understand the Olympiad question.

Their comments:

There is a station at every intersection of two diagonals. (This is not limited to the diagonals that trains run on.) Your map is missing many of these stations.

"Each station lies on the route of at least one train." The routes you have drawn do not service all stations. As such, your map is not valid for the question.

You have to consider all diagonals. All their pairwise intersections are stations and each station must be serviced meaning that of every pair of diagonals that do intersect (inside the polygon) at least one must be active.

Just an extra note, which you may have already noticed, the convex polygon in the diagram looks like it would be disallowed because it has three diagonals which are concurrent.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.