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.

Improve this question
$\endgroup$
8
  • 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$ Commented Jan 23, 2024 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$ Commented Jan 23, 2024 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$ Commented Jan 23, 2024 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$ Commented Jan 23, 2024 at 7:00
  • $\begingroup$ 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$ Commented Jan 23, 2024 at 10:13

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.