MathDB
Problems
Contests
National and Regional Contests
Switzerland Contests
Switzerland Team Selection Test
2023 Switzerland Team Selection Test
5
5
Part of
2023 Switzerland Team Selection Test
Problems
(1)
Graph with Tokyo flavortext
Source: Swiss TST 2023 P5
9/8/2023
The Tokyo Metro system is one of the most efficient in the world. There is some odd positive integer
k
k
k
such that each metro line passes through exactly
k
k
k
stations, and each station is serviced by exactly
k
k
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
S
S
of
k
k
k
stations. He remarks that no three of the stationsin
S
S
S
are on a common metro line. Show that there is some station not in
S
S
S
, which is connected to every station in
S
S
S
by a different metro line.
combinatorics