[ Combinations and Permutations ] $[$ Graph Theory (other) ]

In the parliament, there are 30 deputies. Any two of them are either friends or enemies, and each one is friends with exactly six others. Any three deputies form a committee. Find the total number of committees in which all three members are pairwise friends or all three are pairwise enemies.
In how many committees does a deputy serve? In how many committees do the remaining two members - the deputy's friend and enemy - serve?

## Solution

Let's denote the deputies as points. We will connect the points with a red segment if the corresponding deputies are friends, and with a blue segment if they are enemies.

We need to find the number of monochromatic triangles with vertices at the given points. The number of all triangles is $C_{30}^{3}=4060$.

First, let's count the number of non-monochromatic triangles. In each such triangle, there are exactly two angles where a red and a blue segment meet (let's call such angles mixed). In monochromatic triangles, there are no mixed angles. At each vertex, according to the condition, 6 red and 23 blue segments meet, which means there are $6 \cdot 23=138$ mixed angles with a fixed vertex. Therefore, the total number of non-monochromatic triangles is $138 \cdot 30: 2=2070$. The number of monochromatic triangles is $4060-2070=1990$.

## Answer

1990 committees.

A nut has the shape of a regular hexagonal prism. Each side face of the nut is painted in one of three colors: white, red, or blue, and adjacent faces are painted in different colors. How many different colored nuts exist? (Not all three colors need to be used for the nut's coloring.)

## Solution

Faces of the same color cannot be adjacent, so there are no more than three of them. Let's consider three cases.

1) Only two colors are used - each three times. Then the colors must alternate, and the only coloring scheme (up to rotation) is 121212. By substituting any pair of colors for 1 and 2, we get 3 types of nuts. Swapping the colors in the pair does not change anything.
2) One color is used three times, another twice, and the third once. Clearly, the coloring scheme (up to rotation) is also unique - 121213. Any of the three given colors can be chosen as color 1, and any of the two remaining as color 2. In total, this gives 6 types of nuts.
3) Each color is used twice. Here, there are two sub-cases.

a) Each face is painted the same as the opposite one: the coloring scheme is 123123. There is only one type of nut of this kind (remember that the nut can be flipped).

b) Some opposite faces are painted in different colors (1 and 2). Then the second face of color 1 is next to the first face of color 2, and vice versa, while the faces of color 3 are opposite each other (scheme 123213). It is important which color we choose as color 3, so this results in 3 types of nuts.

In total, $3+6+1+3=13$ types.

