2010 Japan Mathematical Olympiad Finals Problem 3
Source:
February 20, 2011
geometrygeometric transformationrotationgraph theorycombinatorics proposedcombinatorics
Problem Statement
There are islands and bridges connecting them. Suppose that any bridges are connected by one bridge or not the endpoints are connected to 2 distinct islands and we can travel a few times by crossing bridges from each island to any other islands.
Now a letter from each island was sent to some island, note that, some letter may sent to same island, then the following fact was proved that:
In case of connecting island and island by bridge, the habitant of island and that of island are mutually connected by bridge or the same island (itself).
Prove that at least one of the following statements (1) or (2) hold.(1) There exists island for which a letter was sent to the same island.(2) There exist 2 islands, connecting bridge, whose letter are exchanged each other.