Suppose there are 3 islands each for 3 different colors, red, blue and yellow. Try to build several bridges so as to satisfy the following conditions:
* For any pair of islands, they are either connected by a bridge or not connected by any bridge, and every bridge connects two distinct islands.
* For any pair of islands of a same color, there is no bridge connecting the pair, and furthermore, there is no island which is connected to both of the islands in the pair by bridges.
How many ways of building bridges to satisfy these conditions? Building no bridges will be counted as one possibility.
Solution
If the conditions specified in the problem for building bridges are satisfied, then clearly the following modified condition is satisfied:
(†) For any choice of two colors out of the given three, both of the requirements stated for the problem are satisfied if we restrict our consideration only to the islands of the chosen colors and the bridges between those islands.
Conversely, if the condition (†) is satisfied, then we can show that the conditions specified in the problem are satisfied. Indeed, in such a case the first requirement of the problem is clearly satisfied, and to show that the second requirement is satisfied it is enough to show that for any choice of two islands , of the same color and an island of a different color the pair is not connected by any bridge and at least one of the pairs , is not connected by any bridge. But the last assertion follows if we apply (†) to the case of the pairing of colors of () and .
Since two islands of a same color are not connected by any bridge, the answer to the question is given, due to the symmetry, by where is the number of ways of building bridges in the case of 6 islands of two colors (say, red and blue).
So, let us find the value of . By the given requirement, any island connected to a red island by a bridge must be a blue island, and if there is a red island connected with two different blue islands, this would violate the second requirement. So, each red island is connected with at most 1 island (which has to be blue) by a bridge. Similarly, each blue island is connected with at most 1 island (which has to be red) by a bridge. Therefore, to construct bridges, we have to choose islands each from red and blue groups and establish one-to-one correspondence between the sets of 3 red (distinguishable) islands and of 3 blue (distinguishable) islands. This means that there are ways of constructing bridges, and hence we have
and the answer for the problem is given by .