Kvant Math Problem 1500

Represent the group by a simple graph $G$ with $50$ vertices.

kvantmathematicsolympiad

Verified: yes
Verdicts: PASS + PASS
Solve time: 29m05s
Source on kvant.digital

Problem

Prove that in any group of 50 people, there must exist two individuals who have an even number (possibly 0) of mutual acquaintances among the other members of the group.

S. I. Tokarev

City Tournament (Spring, 1995)

Exploration

Represent the group by a simple graph $G$ with $50$ vertices. Two vertices are joined when the corresponding people are acquainted. For vertices $u$ and $v$, the number of mutual acquaintances is the number of common neighbors of $u$ and $v$.

Assume for contradiction that every pair of distinct vertices has an odd number of common neighbors.

Let $A$ be the adjacency matrix of $G$ over the field $\mathbb F_2$. For distinct vertices $i,j$,

$(A^2){ij}=\sum_k a{ik}a_{jk}$

is exactly the number of common neighbors of $i$ and $j$ modulo $2$. Hence

$(A^2)_{ij}=1 \qquad (i\ne j).$

Let $r_i$ denote the $i$th row of $A$. Then

$r_i\cdot r_j=(A^2)_{ij}=1 \qquad (i\ne j).$

The problem becomes a question about $50$ vectors in the $50$-dimensional vector space $\mathbb F_2^{50}$ whose pairwise inner products are all equal to $1$.

The key step is to analyze linear relations among the rows.

Problem Understanding

We must show that the assumption

every pair of vertices has an odd number of common neighbors

is impossible when the graph has $50$ vertices.

The parity condition translates into

$r_i\cdot r_j=1 \qquad (i\ne j),$

where $r_i$ are the rows of the adjacency matrix over $\mathbb F_2$.

The proof proceeds by studying the Gram matrix of these row vectors and deriving a contradiction from the fact that the number of vertices is even.

Proof Architecture

Assume that every pair of distinct vertices has an odd number of common neighbors.

Let $r_1,\dots,r_{50}$ be the rows of the adjacency matrix over $\mathbb F_2$. Their pairwise inner products satisfy

$r_i\cdot r_j=1 \qquad (i\ne j).$

Consider an arbitrary linear relation among the rows. A computation with inner products shows that all rows whose self-inner product is $0$ have the same coefficient, and all rows whose self-inner product is $1$ have coefficient $0$.

This forces all diagonal entries of the Gram matrix to be equal. If they are all $0$, the rows are linearly independent. If they are all $1$, the rows have a one-dimensional space of linear relations.

The first possibility is impossible because the adjacency matrix has zero diagonal. Hence all diagonal entries of the Gram matrix are $1$.

That means every vertex has odd degree, so $A^2=J$, where $J$ is the all-ones matrix. Applying both sides to the all-ones vector yields the final contradiction.

Solution

Suppose, contrary to the statement, that every pair of distinct people has an odd number of mutual acquaintances.

Let $A$ be the adjacency matrix of the corresponding graph, regarded over $\mathbb F_2$, and let $r_1,\dots,r_{50}$ be its rows.

For distinct $i,j$,

$r_i\cdot r_j=(A^2)_{ij}=1.$

Let

$r_i\cdot r_i=\varepsilon_i\in{0,1}.$

Since $r_i\cdot r_i$ is the degree of vertex $i$ modulo $2$, $\varepsilon_i$ records the parity of the degree.

Consider a linear relation

$\sum_{i=1}^{50} c_i r_i=0.$

Taking the inner product with $r_j$ gives

=c_j\varepsilon_j+\sum_{i\ne j}c_i.$$Let$$S=\sum_{i=1}^{50}c_i.$$Then$$0=c_j\varepsilon_j+S+c_j,$$hence$$c_j(\varepsilon_j+1)=S. \tag{1}$$Suppose first that there exist vertices of both parities, so some $\varepsilon_i=0$ and some $\varepsilon_k=1$. From (1), for every index with $\varepsilon_j=1$ we obtain$$0=S.$$For every index with $\varepsilon_j=0$ we obtain$$c_j=S=0.$$Thus all coefficients vanish, and the rows are linearly independent. Therefore $A$ is invertible. Since $A$ is invertible, the relation$$A^2=J+\operatorname{diag}(1+\varepsilon_i)$$shows that $A^2$ is invertible as well. Now choose a vertex with even degree. For such a vertex, $\varepsilon_i=0$, so the diagonal entry $(A^2){ii}$ equals $0$. Hence the $i$th row of $A^2$ is the all-ones vector except for a $0$ in position $i$. Choose also a vertex with odd degree. Its corresponding row of $A^2$ is the all-ones vector. The sum of these two rows is the vector having a single $1$ in position $i$. Consequently the row space of $A^2$ contains a standard basis vector. Repeating this argument for every even-degree vertex shows that the row space contains all standard basis vectors corresponding to even-degree vertices. Since there is at least one odd-degree vertex, the corresponding row is the all-ones vector. Together with those basis vectors, the row space has dimension strictly less than $50$, because every row is generated by the all-ones vector and the basis vectors attached to even-degree vertices. Thus $A^2$ is singular, contradicting the invertibility of $A^2$. Hence vertices of both parities cannot occur. Therefore all $\varepsilon_i$ are equal. Assume next that all $\varepsilon_i=0$. Then (1) becomes$$c_j=S \qquad\text{for all }j.$$Every linear relation therefore has all coefficients equal. Since $50$ is even,$$\sum{i=1}^{50} r_i=0$$would be the only possible nontrivial relation. The vector $\sum_i r_i$ is the vector of vertex degrees modulo $2$. Because all $\varepsilon_i=0$, every degree is even, so indeed$$\sum_{i=1}^{50} r_i=0.$$Thus the rows satisfy exactly one nontrivial relation and$$\operatorname{rank}(A)=49.$$On the other hand, if all $\varepsilon_i=0$, then$$A^2=J+I.$$Over $\mathbb F_2$ and with $50$ even,$$(J+I)x=0$$implies $x=(\sum x_i)\mathbf 1$. Summing the coordinates gives$$\sum x_i=50\sum x_i=0,$$hence $x=0$. Therefore $J+I$ is invertible. Since $A^2=J+I$ is invertible, $A$ must be invertible, contradicting $\operatorname{rank}(A)=49$. Thus the case $\varepsilon_i=0$ for all $i$ is impossible. The only remaining possibility is$$\varepsilon_i=1 \qquad\text{for all }i.$$Every vertex has odd degree. Hence the diagonal entries of $A^2$ are all $1$, while the off-diagonal entries are already known to be $1$. Therefore$$A^2=J.$$Let $\mathbf 1$ be the all-ones vector. Since every degree is odd,$$A\mathbf 1=\mathbf 1.$$Applying $A$ once more,$$A^2\mathbf 1=\mathbf 1.$$But $A^2=J$, and because $50$ is even,$$J\mathbf 1=50,\mathbf 1=0$$in $\mathbb F_2$. Thus$$A^2\mathbf 1=0,$$contradicting$$A^2\mathbf 1=\mathbf 1.$$The contradiction shows that the assumption was false. Hence in every group of $50$ people there exist two individuals who have an even number of mutual acquaintances among the other members of the group. ∎ ## Verification of Key Steps For distinct vertices $i$ and $j$, the entry $(A^2)_{ij}$ counts common neighbors modulo $2$, so the hypothesis translates exactly into$$r_i\cdot r_j=1.$$The relation$$c_j(\varepsilon_j+1)=S$$is obtained by taking inner products of a linear dependence relation with each row. It completely determines the structure of all linear relations among the rows. When all $\varepsilon_i=0$, one obtains $A^2=J+I$. For an even number of vertices, $J+I$ is invertible over $\mathbb F_2$, forcing $A$ to be invertible. This contradicts the existence of the nontrivial relation $\sum r_i=0$. When all $\varepsilon_i=1$, the matrix identity becomes $A^2=J$. Applying both sides to the all-ones vector yields$$\mathbf1=A^2\mathbf1=J\mathbf1=0,$$which is impossible. ## Alternative Approaches The argument can also be phrased in terms of the Gram matrix$$G=(r_i\cdot r_j).$$Under the contrary assumption, $G$ has all off-diagonal entries equal to $1$. The preceding analysis shows that the diagonal entries must all be $1$, which forces $G=J$. The parity of the number of vertices then yields the same contradiction through the action of $J$ on the all-ones vector.