← All Strategies
⊕
Strategy 08 of 12Double Counting
Count the same thing in two different ways
BijectionCombinatoricsGraph Theory
Count the same quantity from two perspectives, then equate the results. This yields a useful relation. Classic: counting handshakes by persons (sum of degrees) or by pairs (twice the number of handshakes).
When to use it
- →When you want to relate two quantities
- →When you have a graph or relation between elements
- →When asked about a sum or count
- →In combinatorics and graph theory
How to think (step by step)
- 1Identify the quantity to count
- 2Count it from perspective 1
- 3Count it from perspective 2
- 4Equate: Perspective 1 = Perspective 2
- 5Derive the desired result
Practice Problems
Three problems at increasing difficulty — try each before revealing the hint or solution.
📘Basic
At a party, \(n\) people shake hands with some others. Let \(d_i\) be person \(i\)'s handshake count. Prove \(d_1 + d_2 + \cdots + d_n\) is even.
📙Intermediate
In a round-robin tournament (\(n\) teams, each plays each other once, no ties), with \(w_i\) wins and \(l_i\) losses for team \(i\), prove \(\sum w_i^2 = \sum l_i^2\).
📕Advanced
Let \(A\) be an \(n \times n\) \((0,1)\)-matrix where every row and column sum equals \(k\). Prove \(A\) contains a permutation matrix (n ones, no two in the same row or column).