Problem

Source: Swiss TST 2023 P5

Tags: combinatorics



The Tokyo Metro system is one of the most efficient in the world. There is some odd positive integer $k$ such that each metro line passes through exactly $k$ stations, and each station is serviced by exactly $k$ metro lines. One can get from any station to any otherstation using only one metro line - but this connection is unique. Furthermore, any two metro lines must share exactly one station. David is planning an excursion for the IMO team, and wants to visit a set $S$ of $k$ stations. He remarks that no three of the stationsin $S$ are on a common metro line. Show that there is some station not in $S$, which is connected to every station in $S$ by a different metro line.