Combinatorics Post # 1: Double Counting
by niyu, Jul 1, 2017, 5:52 AM
In this post, I'll be talking about double counting. This is mainly to set the stage for future combinatorics posts, in which this fundamental technique will be used extensively.
Heuristics: Double Counting is probably the most fundamental concept in combinatorics. The main idea of double counting is to count some quantity in two different ways. Often, the main difficulty of a double counting problem is the figuring out the specific quantity to double count. In this post, I'll be showing several problems that highlight this technique.
Let's begin!
The following problem is a very basic double counting problem, but it highlights the kinds of things that come up in this technique well.
Problem 1:
Solution
Our next problem is from combinatorial geometry.
Problem 2: IMO 1989/3
Solution
The following
problems are more challenging examples of this technique.
Problem 3: IMO 1998/2
Solution
Problem 4: Iran Olympiad
Solution
Problem 5: Russia 1999
Solution
Problem 6: USAMO 2011/6
Solution
To conclude, we present a problem from the USA TST.
Problem 7: USA December TST 2014/3
Solution: "Use Obvious Inequalities" - Gabriel Dospinescu
Heuristics: Double Counting is probably the most fundamental concept in combinatorics. The main idea of double counting is to count some quantity in two different ways. Often, the main difficulty of a double counting problem is the figuring out the specific quantity to double count. In this post, I'll be showing several problems that highlight this technique.
Let's begin!
The following problem is a very basic double counting problem, but it highlights the kinds of things that come up in this technique well.
Problem 1:
Let
be a set of
persons such that:



- any person is acquainted to exactly
other persons in
;
- any two persons that are acquainted have exactly
common acquaintances in
;
- any two persons that are not acquainted have exactly
common acquaintances in
.

Solution
We double count triplets
, where
and
are two people in
and
is a common acquaintance of the two.
Count 1: Pick a person
. Then, there are
people
is acquainted to. If we choose any two of these people, they clearly form a triplet of the form we want. Since there are
people total, there are
such triplets.
Count 2: We now count by cases: when
and
are acquainted, and when they are not acquainted. Fix
. If
knows
, there are
choices for
. Since the order in which we choose these people is irrelevant and there are
choices for
, there are
such pairs
. We are given that
and
have
common acquaintances in
, so there are
such triplets where
and
are acquainted.
If
and
are not acquainted, after fixing
, there are
choices for
(make sure you see why this isn't
- we don't want
to be counted in the set of such
). Since there are
choices for
, and order is irrelevant, there are
such pairs
and
. We are given that
and
have
common acquaintances in
, so there are
such triplets where
and
are not acquainted.
It follows that there are
such triplets.
Thus,






Count 1: Pick a person





Count 2: We now count by cases: when


















If




















It follows that there are

Thus,

Our next problem is from combinatorial geometry.
Problem 2: IMO 1989/3
Let
and
be positive integers and let
be a set of
points in the plane such that
(a) no three points of
are collinear, and
(b) for every point
of
there are at least
points of
equidistant from 
Prove that




(a) no three points of

(b) for every point





Prove that

Solution
Define
as the number of isosceles triangle. We double count
. We count them in the following two ways: by apex and by vertices.
We first count by apex. Fix a given point
. Since there are at least
points equidistant from
, there are at least
ways to select the other two vertices in order to get an isosceles triangle. Since there are
choices for
, 
We now count by vertices. Pick two points in
,
and
. To get an isosceles triangle
,
must lie on the perpendicular bisector of
. Since no three points are collinear, there are at most
choices for
. Since there are
ways to pick
and
, 
Hence,
Thus,



We first count by apex. Fix a given point







We now count by vertices. Pick two points in












Hence,


The following

Problem 3: IMO 1998/2
In a contest, there are
candidates and
judges, where
is an odd integer. Each candidate is evaluated by each judge as either pass or fail. Suppose that each pair of judges agrees on at most
candidates. Prove that ![\[{\frac{k}{m}} \geq {\frac{n-1}{2n}}. \]](//latex.artofproblemsolving.com/3/8/7/387c8824b28f6422306e3c25b34fccb0a841f4cd.png)




![\[{\frac{k}{m}} \geq {\frac{n-1}{2n}}. \]](http://latex.artofproblemsolving.com/3/8/7/387c8824b28f6422306e3c25b34fccb0a841f4cd.png)
Solution
We double count triplets
, where
and
are judges, and candidate
is agreed upon by the two judges. Let
be the number of such triplets.
We first count by pairs of judges. Pick two judges,
and
. Then, there are at most
candidates
and
agree upon. Since there are
choices for
,
.
Next, we count by candidates. Let
be the number of judges who PASS candidate
. We find that
, where the sum ranges across all candidates.
The rest of the solution is just boring algebra. We include it here for completeness.
By convexity, we have (recall that
is odd)
Since there are
candidates, we find that
Thus,






We first count by pairs of judges. Pick two judges,








Next, we count by candidates. Let



The rest of the solution is just boring algebra. We include it here for completeness.
By convexity, we have (recall that





Problem 4: Iran Olympiad
A school has
students. Each student can participate in any number of classes that he wants. Every class has at least two students participating in it, and if two different classes have at least two common students, then the number of students in these two classes is different. Prove that the number of classes is not greater than
.


Solution
We double count pairs
, where
is a class containing exactly
students. Define a function
, where
denotes the number of classes containing exactly
students. Also, there are
pairs of students in each of these classes. It follows that there are
pairs of students in classes containing exactly
students. We must have
, so that
for all
.
Finally, note that the number of classes is
. Letting the number of classes be
, we get
After some partial fraction decomposition and telescoping, the last sum becomes
.
Thus,













Finally, note that the number of classes is




Thus,

Problem 5: Russia 1999
In a class, every boy knows at least one girl. Prove that there is a group containing at least half of the students such that each boy in the group knows an odd number of girls in the group.
Solution
We double count pairs
, where
is a boy knowing an odd number of girls in some set of girls
.
We first count by boys. Let
denote the number of girls a given boy
knows,
be the number of girls, and
be the total number of students. It follows that there are
ways to choose an odd number of girls
knows. There are then
ways to pick the girls that
doesn't know in
. It follows that there are
possible sets
for
. Since there are
boys, it follows that there are
pairs.
Next, we count by sets of girls. Let
be the set of boys knowing an odd number of girls in a set of girls
. It follows that there are
such pairs. Therefore,

We claim that there must be some set
for which
. We prove this by contradiction: suppose
that
. Then, since there are
sets of girls,
. Since
is a set of boys and
is a set of girls, we find that
. Hence,
Note that
. Hence,
This is impossible, since
. Therefore, there must be some set
for which
. This set satisfies the problem, as each boy in the set knows an odd number of girls in the set, and the size of the set is more than half the size of the class. This completes the proof.



We first count by boys. Let














Next, we count by sets of girls. Let




We claim that there must be some set















Problem 6: USAMO 2011/6
Let
be a set with
, meaning that
has 225 elements. Suppose further that there are eleven subsets
of
such that
for
and
for
. Prove that
, and give an example for which equality holds.










Solution
We double count triplets
where
.
We first count by pairs of sets. Given any two sets
and
, we know that
. Since there are
possibilities for
, there are
such triplets.
Next, we count by elements. Let
be the number of sets
is in. There are then
(where the sum ranges across all
) such triplets.
Hence,
.
The rest of the solution is just algebra.
Let
. By Jensen,
Thus,
. Equality holds for example when
. 


We first count by pairs of sets. Given any two sets






Next, we count by elements. Let




Hence,

The rest of the solution is just algebra.
Let





To conclude, we present a problem from the USA TST.
Problem 7: USA December TST 2014/3
Let
be an even positive integer, and let
be an
-vertex graph with exactly
edges, where there are no loops or multiple edges (each unordered pair of distinct vertices is joined by either 0 or 1 edge). An unordered pair of distinct vertices
is said to be amicable if they have a common neighbor (there is a vertex
such that
and
are both edges). Prove that
has at least
pairs of vertices which are amicable.










Solution: "Use Obvious Inequalities" - Gabriel Dospinescu
We count amicable pairs, and as the title of this solution suggests, we use extremely dumb bounds, which actually manage to solve this problem. This bound is: the max of some numbers
is at least the average of these numbers.
Let
for convenience, so that
has
edges.
We count amicable pairs a given vertex is
is in. Let
be an arbitrary neighbor of
. Using the aforementioned bound, we find that
is in at least
amicable pairs.
Summing across all
, we find that there are at least
where the sums range across all
, and all
that are neighbors of
, respectively (we divide by
since each amicable pair contain
vertices, and order is irrelevant). We can now rewrite this sum as
Applying AM-GM, we find that there are at least
amicable pairs. Note that each unordered pair
corresponds to an edge in
, since
and
are neighbors. Hence,
. It follows that there are at least
amicable pairs. Recall that
. Thus, there are at least
amicable pairs, as desired. 

Let



We count amicable pairs a given vertex is





Summing across all

![\begin{eqnarray*}
\frac{1}{2}\sum \left[\frac{\sum \deg (B)}{\deg{(A)}} - 1\right] & = & \frac{1}{2}\sum\frac{\sum \deg (B)}{\deg{(A)}} - \frac{1}{2}\sum{1} \\
& = & \frac{1}{2}\sum\frac{\sum \deg (B)}{\deg{(A)}} - k \mbox{,}
\end{eqnarray*}](http://latex.artofproblemsolving.com/0/2/d/02da9da53c3d66261e045a7f18039740253999c8.png)





![\begin{eqnarray*}
\frac{1}{2}\sum_{\{A, B\}}\left[\frac{\deg (A)}{\deg{(B)}} + \frac{\deg{(B)}}{\deg{(A)}}\right] - k \mbox{,}
\end{eqnarray*}](http://latex.artofproblemsolving.com/7/0/a/70ad1cfa53895cab944e1b2cdc8bd5b9f2dba682.png)










This post has been edited 7 times. Last edited by niyu, Jul 9, 2017, 7:02 PM