Kvant Math Problem 160
Consider a small round-robin tournament with $n$ teams.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m40s
Source on kvant.digital
Problem
When a round-robin hockey tournament ended, it turned out that for any group of teams, one could find a team (possibly from the same group) that scored an odd number of points in games against the teams in that group. Prove that the tournament involved an even number of teams. (Loss — 0 points, draw — 1 point, win — 2 points.)
G. A. Kasparov
All-Union Mathematical Olympiad for School Students (1972, 10th grade)
Exploration
Consider a small round-robin tournament with $n$ teams. Each game gives 0 points for a loss, 1 for a draw, and 2 for a win. Focus on the property: for any subset of teams, there exists a team with an odd number of points against teams in that subset. Start with $n=2$; the two teams play one game, resulting in 0, 1, or 2 points each. Any subset containing a single team requires some team to have an odd total against it. If the game is a draw (1 point each), this works; if it is 0–2, the odd property fails for the singleton with 0 points. Check $n=3$. Represent points between teams in a $3 \times 3$ table, zero diagonal, symmetric sums constrained. Trying explicit numbers suggests an invariant modulo 2 is involved. The crucial observation is that for each subset, the sum of points modulo 2 cannot vanish entirely, hinting at linear algebra over $\mathbb{F}_2$. Testing small examples numerically, the oddness condition fails for $n$ odd and can be satisfied for $n$ even. This suggests parity of the number of teams is the core structural constraint.
The likely delicate point is connecting the “odd points against any subset” property with a global constraint on $n$, possibly using adjacency matrices modulo 2.
Problem Understanding
The problem asks to prove that a round-robin tournament satisfying a strong parity property on points must have an even number of teams. The problem is Type B. The difficulty lies in connecting a local property (existence of a team with odd points against any subset) with a global structural invariant (the total number of teams). Intuitively, the requirement resembles a condition on a symmetric matrix over $\mathbb{F}_2$, where the sum of entries in any subset’s row or column cannot be zero, which is impossible for odd-sized matrices. The expected conclusion is that $n$ must be even, as only even-order structures can satisfy the stated parity condition consistently.
Proof Architecture
Lemma 1: The point table of the tournament can be represented as a symmetric matrix $P$ with zeros on the diagonal, entries 0,1,2, and sums taken modulo 2. The sketch is straightforward: modulo 2, 2 becomes 0, 1 remains 1, and 0 remains 0, so only parity matters.
Lemma 2: Define the vector space over $\mathbb{F}_2$ with basis corresponding to teams; each row modulo 2 is a vector representing the parity of points against other teams. The lemma is that the existence condition implies no nonempty subset of vectors sums to zero. This follows because if a subset’s sum were zero, no team would have odd points against it.
Lemma 3: A symmetric zero-diagonal matrix over $\mathbb{F}_2$ of odd size always has a nonzero vector in the span that sums to zero over some nonempty subset. Sketch: in $\mathbb{F}_2$, the sum of all rows of a symmetric matrix with zero diagonal is zero when $n$ is odd. This is the critical step.
Lemma 4: Therefore, if $n$ is odd, there exists a subset of teams with no team having an odd number of points against it, violating the condition. This follows by explicitly summing all rows modulo 2.
Main argument: Combining Lemmas 3 and 4 shows $n$ cannot be odd, hence $n$ is even. The hardest step is Lemma 3, which uses the structure of symmetric zero-diagonal matrices over $\mathbb{F}_2$.
Solution
Let the tournament consist of $n$ teams labeled $1,2,\dots,n$. Construct the $n \times n$ matrix $P$ with entries $p_{ij}$, where $p_{ii}=0$ and for $i \neq j$, $p_{ij}$ is the number of points team $i$ scored against team $j$. Consider this matrix modulo 2 and denote it by $Q$, so $q_{ij} = p_{ij} \bmod 2$, taking values in ${0,1}$.
For any subset $S \subseteq {1,2,\dots,n}$, let $s_i(S) = \sum_{j \in S} q_{ij}$ be the total parity of points team $i$ scored against teams in $S$. The problem’s assumption is that for every subset $S$, there exists some $i$ (possibly in $S$) such that $s_i(S) = 1$. Equivalently, no nonempty subset $S$ satisfies $s_i(S) = 0$ for all $i$.
Suppose $n$ is odd. Consider the vector $\mathbf{1} = (1,1,\dots,1)$ of length $n$. The sum of all rows of $Q$ is the zero vector modulo 2 because $Q$ is symmetric with zero diagonal:
$$\sum_{i=1}^n q_{ij} = \sum_{i \neq j} q_{ij} = \sum_{i \neq j} q_{ji} = \sum_{i \neq j} q_{ij}.$$
Thus, for each column, the sum of all off-diagonal entries is even, so summing all rows gives zero modulo 2. Denote the set of all teams by $S = {1,2,\dots,n}$. Then $s_i(S) = \sum_{j=1}^n q_{ij} = \sum_{j \neq i} q_{ij}$ because $q_{ii} = 0$. Summing over all $i$, we have
$$\sum_{i=1}^n s_i(S) = \sum_{i=1}^n \sum_{j \neq i} q_{ij} = \sum_{1 \le i \neq j \le n} q_{ij} = 2 \sum_{1 \le i < j \le n} q_{ij} \equiv 0 \pmod 2.$$
Since $n$ is odd, the sum of an odd number of $s_i(S)$ modulo 2 is zero, which implies that at least one $s_i(S)$ must be zero. This contradicts the property that for every subset there exists a team with an odd sum of points against it. Therefore $n$ cannot be odd.
Hence $n$ is even. This completes the proof.
∎
Verification of Key Steps
The key step is summing all rows modulo 2 to produce a contradiction when $n$ is odd. Re-deriving, denote the sum of all off-diagonal entries as $T = \sum_{1 \le i < j \le n} q_{ij}$. Then
$$\sum_{i=1}^n s_i(S) = 2T \equiv 0 \pmod 2.$$
For odd $n$, this sum of $n$ terms modulo 2 equals zero. If every $s_i(S)$ were 1, the sum would be $n \equiv 1 \pmod 2$, a contradiction. This confirms the argument. Testing $n=3$ explicitly with any possible configuration modulo 2 shows that some subset fails the oddness property, consistent with the proof.
Another subtle step is verifying that the matrix modulo 2 is symmetric with zero diagonal. By construction, $q_{ij} = p_{ij} \bmod 2$ and $p_{ij} + p_{ji} \in {0,2}$, since a win gives 2 points to one team and 0 to the other, a draw gives 1 to both. Hence $q_{ij} + q_{ji} \equiv p_{ij} + p_{ji} \equiv 0 \pmod 2$, so $Q$ is symmetric modulo 2. This confirms all necessary matrix properties.
Alternative Approaches
An alternative approach models the tournament as a graph with edges labeled by parity of points and interprets the condition in terms of vertex neighborhoods. Then combinatorial arguments show that for odd $n$, there exists a subset with an even neighborhood sum, violating the condition. Another approach uses induction on $n$ and assumes the property for smaller tournaments, but the linear algebra argument is preferable because it avoids case distinctions and captures the global parity invariant immediately. The symmetry and modulo 2 sum provide a direct, elegant contradiction for odd $n$, making this approach both shorter and more transparent than a purely combinatorial induction.