What is Double Counting?

Solution 1:

"Double counting" or more accurately "counting in two ways" is a combinatorial technique. It is used for showing that two expressions are equal by demonstrating that they are two ways of counting the size of same set, or to derive other conclusions from the equality of two expressions.

It is often used to prove combinatorial identities such as $$\binom{n}{0}+\binom{n}{1}+\ldots+\binom{n}{n}=2^n$$

LHS counts total number of subsets of an $n$-set according to their size. RHS also counts total number of subsets according to the choice of any element being present or not. Hence the two expressions must be equal.

For another use, let us consider your problem as example.

An exercise sheet with 9 tasks was distributed to 7 students. Each student must complete at least 4 assignments. Show by double counting that there is at least one task that has been completed by at least 4 students.

Here you can count the total number of tasks completed one way, by counting number of tasks done by each of $7$ students. If $i$th student submits $x_i$ tasks then according to given condition, $$28 \le x_1+\ldots+x_7 \le 63$$

Another way to count the same total number is asking how many students solved task number $1$, $2$, etcetera. If $y_j$ is the number of students who solved $j$th task, then total number of tasks completed is $$y_1+y_2+\ldots+y_9 = x_1+\ldots+x_7$$ From this equality, conclude $$28 \le y_1+y_2+\ldots+y_9 \le 63$$

The lower bound can be achieved if and only if atleast one of $y_j$ is greater than or equal to $4$ (since $9\times3 = 27 < 28$). This completes the proof.