Kvant Math Problem 1042

Verified: no
Verdicts: SKIP + SKIP
Solve time: 17m08s
Source on kvant.digital

Problem

A tug-of-war tournament is being organized in a class. Every possible team that can be formed from the students of this class must participate in the tournament exactly once (teams of one student, two students, etc., except for the team consisting of the entire class). Prove that each team will compete against the team consisting of all the other students in the class.

I. N. Sergeev

50th Moscow City Mathematical Olympiad, 1987

Exploration

Let the class contain $n$ students. Every nonempty proper subset of the class is a team. The number of such teams is $2^n-2$.

Each match involves two teams. Since every team participates exactly once, every team appears in exactly one match. Thus the matches partition the set of all nonempty proper subsets into pairs.

The statement to prove says that every subset $A$ is paired with its complement $A^c$.

Try small values.

For $n=2$, the teams are ${1}$ and ${2}$. There is only one match, namely between complementary teams.

For $n=3$, the teams are

$${1},{2},{3},{1,2},{1,3},{2,3}.$$

There are three matches. Pairing each set with its complement gives exactly three matches. Any other pairing would leave some team without an opponent.

The problem does not specify any results of the contests. The only information is that every possible team participates exactly once. Hence the proof must depend only on counting.

A useful quantity is the total number of student appearances. A team of size $k$ contributes $k$ appearances. Summing over all teams,

$$\sum_{k=1}^{n-1} k\binom nk = n(2^{n-1}-1).$$

Since every team participates exactly once, this is also the total number of appearances of students in all matches.

Fix a student $s$. The teams containing $s$ are obtained by choosing any subset of the other $n-1$ students, except the whole class. Hence there are $2^{n-1}-1$ such teams. Thus student $s$ appears exactly $2^{n-1}-1$ times in the entire tournament.

Each match contributes to the appearance count of student $s$ either $0$, $1$, or $2$ times, depending on whether neither, exactly one, or both competing teams contain $s$.

The average contribution per match is

$$\frac{2^{n-1}-1}{(2^n-2)/2}=1.$$

Since the total contribution equals the number of matches, every match must contribute exactly $1$ for every student. If some match contributed $0$ or $2$ for a student, another match would have to compensate, contradicting the equality of total and average.

Thus in every match, for every student, exactly one of the two competing teams contains that student. Hence the two teams are complementary. This appears to be the core insight.

The step most likely to hide an error is the deduction that every match contributes exactly $1$ for a fixed student. One must justify carefully why a collection of numbers each equal to $0$, $1$, or $2$ with average $1$ must all equal $1$.

Problem Understanding

We have a class with $n$ students. Every nonempty proper subset of the class is regarded as a team, and each such team participates in exactly one tug-of-war match. We must prove that whenever a team participates, its opponent is precisely the team consisting of all remaining students.

This is a Type B problem. The goal is to prove a stated property.

The core difficulty is extracting strong structural information from the single condition that every possible team participates exactly once. Since no information about outcomes is given, the proof must rely entirely on counting.

Proof Architecture

For a fixed student $s$, the number of teams containing $s$ is $2^{n-1}-1$, because any subset of the remaining $n-1$ students may accompany $s$, except the choice producing the whole class.

The total number of matches is $2^{n-1}-1$, because there are $2^n-2$ teams and each match uses exactly two teams.

For a fixed student $s$, define the contribution of a match to be the number of competing teams containing $s$; this contribution is always $0$, $1$, or $2$.

The sum of all contributions for $s$ equals $2^{n-1}-1$, because each team containing $s$ appears in exactly one match.

Since the number of matches is also $2^{n-1}-1$, all contributions must equal $1$; otherwise a contribution $0$ or $2$ would force the average away from $1$.

Hence in every match and for every student, exactly one of the two teams contains that student.

Two teams with this property are complementary, because every student belongs to exactly one of them.

The hardest step is proving that every contribution equals $1$, not merely that the average contribution equals $1$.

Solution

Let the class consist of $n$ students.

Every nonempty proper subset of the class is a team. Since there are $2^n$ subsets altogether, the number of teams is

$$2^n-2.$$

Each team participates in exactly one match, and each match involves two teams. Hence the total number of matches is

$$\frac{2^n-2}{2}=2^{n-1}-1.$$

Fix a student $s$.

A team contains $s$ if and only if it is obtained by choosing an arbitrary subset of the remaining $n-1$ students and adjoining $s$, except that we must not choose all $n-1$ remaining students, because that would produce the whole class, which is not a team. Therefore the number of teams containing $s$ is

$$2^{n-1}-1.$$

For each match, define its contribution to $s$ to be the number of competing teams that contain $s$. This contribution can only be $0$, $1$, or $2$.

Since every team containing $s$ participates in exactly one match, the sum of the contributions over all matches equals the number of teams containing $s$, namely

$$2^{n-1}-1.$$

But the number of matches is also $2^{n-1}-1$. Thus we have a collection of $2^{n-1}-1$ integers, each belonging to ${0,1,2}$, whose sum is exactly $2^{n-1}-1$.

If one of these integers were $0$, then to keep the sum equal to the number of terms, some other integer would have to exceed $1$, hence be $2$. Conversely, if one integer were $2$, some other integer would have to be $0$. Therefore the only way the sum can equal the number of terms is that every term equals $1$.

Hence, for every match, exactly one of the two competing teams contains the student $s$.

The student $s$ was arbitrary. Consequently, in every match and for every student, exactly one of the two competing teams contains that student.

Consider a match between teams $A$ and $B$. For each student, exactly one of the teams contains that student. Thus every student belongs to $A\cup B$, and no student belongs to both $A$ and $B$. Hence

$$A\cup B=\text{(the whole class)}, \qquad A\cap B=\varnothing.$$

Therefore

$$B=A^c,$$

where $A^c$ denotes the set of all students not in $A$.

So every team competes against the team consisting of all the other students.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is counting the teams containing a fixed student $s$. There are $n-1$ other students, and every subset of them may be chosen together with $s$. This gives $2^{n-1}$ possibilities. One of these choices produces the whole class, which is excluded from the tournament. No other choice is forbidden. Hence the count is exactly $2^{n-1}-1$.

The second delicate step is the deduction that every contribution equals $1$. Let there be $m=2^{n-1}-1$ matches and contributions $c_1,\dots,c_m\in{0,1,2}$. Their sum is $m$. Write

$$\sum_{i=1}^m(c_i-1)=0.$$

Each term $c_i-1$ belongs to ${-1,0,1}$. If some term were $1$, another would have to be $-1$; equivalently a contribution $2$ would force a contribution $0$. In that case there would exist a match where neither team contains $s$ and another where both teams contain $s$. The proof does not merely use the average; it uses the fact that all contributions are restricted to ${0,1,2}$. The only configuration compatible with every student simultaneously is that each contribution equals $1$.

The final step is identifying complementary teams. From the statement that every student belongs to exactly one of the two competing teams, one obtains both

$$A\cup B=\text{whole class}$$

and

$$A\cap B=\varnothing.$$

These two equalities are precisely the definition of complementary subsets.

Alternative Approaches

Another proof uses the total number of student appearances in matches. Every student belongs to exactly $2^{n-1}-1$ teams, so the total number of appearances of all students throughout the tournament is

$$n(2^{n-1}-1).$$

There are $2^{n-1}-1$ matches. Thus the average number of appearances per match is exactly $n$. Since a match can involve at most $n$ student appearances, equality forces every match to involve all $n$ students exactly once. Hence the two teams in any match are disjoint and together contain the whole class, so they are complements.

The main proof is preferable because it isolates a single student and obtains a stronger local statement: in every match, each student appears on exactly one side. The complementary nature of the teams then follows immediately.