Question 173
Suppose there are $2010$ islands, and $2009$ bridges connecting some pair of these islands. Any pair of islands are either connected by one of the bridges or they are not. Also, any bridge connects two different islands. Furthermore, one can reach any island from any other island by crossing certain number of bridges. One day, each of the islands sent a letter to some island (possibility of sending the letter to itself was allowed). After the letters were delivered, the following facts came to light:
For islands $A$ and $B$ which are connected by a bridge, the addressee of the letter from $A$ and the addressee of the letter from $B$ are either connected by a bridge or else they are the same island.
Show that in this situation at least one of the following statements must be valid:
(1) There must be an island which sent its letter to itself.
(2) There is a pair of islands connected by a bridge, which exchanged letters.
For islands $A$ and $B$ which are connected by a bridge, the addressee of the letter from $A$ and the addressee of the letter from $B$ are either connected by a bridge or else they are the same island.
Show that in this situation at least one of the following statements must be valid:
(1) There must be an island which sent its letter to itself.
(2) There is a pair of islands connected by a bridge, which exchanged letters.