Suppose a company's board of directors is composed of individuals. Each of these individuals has precisely enemies on the board, the remaining members being friends. (Being enemies or friends is not a one-sided affair, i.e., any two board members are either enemies of one another or friends of one another.)
In how many ways can a member subcommittee be formed such that its members are either all friends or all enemies?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Configure 2 0 points in a circular pattern separated by equal distances. These points represent the 2 0 board members. With these points we can form ( 3 2 0 ) = 1 1 4 0 distinct triangles.
Now represent enemy pairings as a red line joining two points and friendships as a blue line joining two points. Now let the number of possible 3 -person subcommittees that are not either all friends or all enemies be N . Each of these N triangles has 2 of its vertices at the end of both a red and a blue line for a total of 2 N vertices.
Now each of the 2 0 points lies at one end of 6 red lines and 1 3 blue lines. So each of the points will be part of 6 ∗ 1 3 = 7 8 triangles which have sides which are not all the same color. This is the case for each of the 2 0 points, and these 2 0 ∗ 7 8 = 1 5 6 0 triangle vertices correspond to the 2 N vertices discussed above. Thus
2 N = 1 5 6 0 ⟹ N = 7 8 0 .
But the desired number of "all friend or all enemy" subcommittees will just be the complement N , so the solution is 1 1 4 0 − 7 8 0 = 3 6 0 .