In many combinatorics problems, it is useful to count a quantity in two ways. Let’s start with a simple example.

(Iran 2010 \#2) There are points in the plane such that no three of them are collinear. Prove that the number of triangles, whose vertices are chosen from these points and whose area is , is not greater than .

Let the number of such triangles be . For each edge between two points in the set we count the number of triangles it is part of. Let the total number over all edges be .

On the one hand, for any edge , there are at most points such that the triangles they form with and have the same area. This is because those points have to be the same distance from line , and no three of them are collinear. Thus, . On the other hand, each triangle has edges, so . Thus,

It’s a good idea to consider double counting if the problem involves a pairing like students and committees, or an array of numbers; it’s also often useful in graph theory problems.

(IMO 1987 #1) Let be the number of permutations of the set which have exactly fixed points. Prove that

The first idea that might occur here would be to find , then multiply it by , sum it up… probably resulting in a big expression. However, if we look at the required result, we see that it suggests a natural counting — the left-hand side is the total number of fixed points over all permutations. Another way to obtain that is to consider that each element of is a fixed point in permutations, so the total is . (Note that we are counting pairs of the form (point, permutation) such that the point is a fixed point of the permutation.)



(China Hong Kong MO 2007) In a school there are 2007 girls and 2007 boys. Each student joins no more than 100 clubs in the school. It is known that any two students of opposite genders have joined at least one common club. Show that there is a club with at least 11 boys and 11 girls.

Since we are only given information about club membership of students of different gender, this suggests that we should consider triples of the form (boy, girl, club), where the boy and girl both attend the club. Let the total number of such triples be .

For each pair (boy, girl), we know that they attend at least one club together, so since there are such pairs,

Assume that there is no club with at least 11 boys and 11 girls. Let be the number of triples involving clubs with at most 10 boys, and be the number of triples involving clubs with at most 10 girls. Since any student is in at most 100 clubs, the number of (girl, club) pairs is at most , so . Similarly, . Then,
which is a contradiction.

If is an integer and is a prime, then

Consider the set of strings of length using an alphabet with different symbols. Note that these strings can be separated into equivalence classes, where two strings are equivalent if they are rotations of each other. Here is an example of such an equivalence class (called a "necklace") for :

Let’s call a string with at least two distinct symbols in it \textit{non-trivial}. All the rotations of a non-trivial string are distinct — since is prime, a string cannot consist of several identical substrings of size greater than . Thus, all the equivalence classes have size , except for those formed from a trivial string, which have size .

Thus, there are two ways to count the number of non-trivial strings. Since there are strings in total, of which are trivial, we have non-trivial strings. Also, the number of non-trivial strings is times the number of equivalence classes formed by non-trivial strings. Therefore, divides .


might contain mistakes