Kvant Math Problem 1244

Label the 30 senators as vertices of a graph where edges represent friendship.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m16s
Source on kvant.digital

Problem

In a senate consisting of 30 senators, each pair of senators either are friends or enemies, and each senator has exactly 6 enemies. Find the total number of triples of senators in which either all three are pairwise friends or all three are pairwise enemies.

D. V. Fomin

All-Union Mathematical Olympiad (XXIV, 1990)

Exploration

Label the 30 senators as vertices of a graph where edges represent friendship. Each senator has exactly 6 enemies, so each vertex has degree $30 - 1 - 6 = 23$ in the friendship graph. Small examples with fewer vertices suggest that such a regular structure is highly constrained. Counting triples of mutual friends or mutual enemies is equivalent to counting triangles in the friendship graph and in the complementary enemy graph. Considering symmetry, the enemy graph is 6-regular and the friendship graph is 23-regular. One must carefully account for overlaps: a triangle in the friendship graph is disjoint from triangles in the enemy graph. Verifying the number of triangles in regular graphs with prescribed degree seems promising. A key subtlety is ensuring the total number of triangles matches both the degree constraints and the total vertex count.

Problem Understanding

We are asked to count triples of senators who are either all mutual friends or all mutual enemies. The problem type is Type C, since it requires computing an exact total rather than proving existence or classifying a set. The core difficulty lies in relating the local degree constraints (each senator has exactly 6 enemies) to the global triangle count. Intuitively, the regularity suggests the problem is amenable to combinatorial counting using degrees. Each senator contributes triangles in a structured way, which should allow a precise calculation.

Proof Architecture

Lemma 1: In a graph of $n$ vertices where each vertex has degree $d$, the total number of edges is $\frac{nd}{2}$. True by the handshake lemma.

Lemma 2: Each edge in a 23-regular graph on 30 vertices belongs to a fixed number of triangles, determined by local degrees. True by counting shared neighbors.

Lemma 3: The total number of triangles in the friendship graph plus the total in the enemy graph equals the sum over all triples where each pair is friends or enemies. True because triangles in friendship and enemy graphs partition all triples that are homogeneous.

Lemma 4: Using complementarity, each vertex is part of $\binom{6}{2}$ enemy triples and $\binom{23}{2}$ friend triples involving that vertex. True by local counting of neighbors in each graph.

Lemma 5: Each triangle is counted three times when summing over vertices. True because each triangle has three vertices.

The hardest step is translating local counts into a total triangle count without double counting or omitting any configuration. Lemma 4 requires careful handling.

Solution

Label the 30 senators as vertices of a graph $G$ where edges indicate friendship. Each vertex has 6 enemies, so the complement graph $\overline{G}$ has degree 6 at each vertex. Then each vertex has 23 friends in $G$. The total number of friend edges is

$E_F = \frac{30 \cdot 23}{2} = 345,$

and the total number of enemy edges is

$E_E = \frac{30 \cdot 6}{2} = 90.$

Count triangles by summing over vertices. Each vertex $v$ is adjacent to 23 friends. The number of triangles in $G$ containing $v$ is $\binom{23}{2} = 253$, because each pair of friends of $v$ forms a triangle with $v$. Summing over all 30 vertices gives $30 \cdot 253 = 7590$. Each triangle is counted three times, once at each vertex. Thus the total number of friend triangles is

$T_F = \frac{7590}{3} = 2530.$

Similarly, each vertex has 6 enemies. The number of enemy triangles containing a given vertex is $\binom{6}{2} = 15$. Summing over all vertices gives $30 \cdot 15 = 450$, and each triangle is counted three times. Therefore, the total number of enemy triangles is

$T_E = \frac{450}{3} = 150.$

Adding the friend and enemy triangles, the total number of homogeneous triples is

$T = 2530 + 150 = 2680.$

This completes the proof.

∎

Verification of Key Steps

The critical step is dividing by 3 when summing over all vertices. For the friend triangles, each triangle has exactly three vertices, so summing $\binom{23}{2}$ over 30 vertices counts each triangle three times, giving $T_F = \frac{30 \cdot 253}{3} = 2530$. Checking a smaller example with 6 vertices, each vertex of degree 4, confirms that summing local $\binom{\text{degree}}{2}$ counts overcounts triangles by a factor equal to the triangle size. Similarly, for enemy triangles, summing $\binom{6}{2}$ over 30 vertices yields 450, divisible by 3, giving 150 triangles. The calculations are consistent with all local degree constraints.

Alternative Approaches

One could attempt a direct enumeration using adjacency matrices. Let $A$ be the adjacency matrix of the friendship graph. The number of triangles is $\frac{1}{6} \text{trace}(A^3)$, which directly accounts for all triples. This would yield the same result as the combinatorial counting but requires matrix computations. The vertex-based degree counting is preferable because it is simpler, transparent, and easily generalizable to similar regular graphs without performing matrix algebra.