Skip to main content

The Art of Double Counting

Hey everyone I'm Bratin and I'm a class 10 student hailing from Kolkata. I've been into math contests for a while now and enjoy combinatorics and geometry the most. In this post I'll dive into the topic of double counting by working through some problems and hopefully be able to showcase how to employ the technique when the need arises for the same.   

Put simply, double counting is basically counting in two different ways (duh). The main goal is to count a single quantity in $2$ different ways. There really is no theoretical concepts attached to it. It's just basically elementary combinatorics with ingenuity since you need to figure out what are the $2$ "ways" in which you can consider counting. Below are few problems to get you started. I've discussed the solutions to all of the problems mentioned, with motivation/comments. It is however advisable that the readers try their hand independently at them before moving on to read the solutions.  

(IMO 1987 #1) Let $p_n(k)$ denote the number of permutations of the set $\{1,2,3,\dots,n\}$ which have exactly $k$ fixed points. Prove that $$\sum_{k = 0}^{n} k_{p_{n}}(k) = n!$$

Motivation  Here's a tip: Whenever there are complex notations involved (usually sigma or the product notation) try your best to simplify it or try out small cases to see a pattern. In the above expression, trying out small values of $n$ confirms the fact that the LHS is indeed the total number of fixed points present in the permutation of $\{1,2,3,\dots,n\}$ 

Solution: Observe that the left side of the expression is the total number of fixed points present in the permutation of $\{1,2,3,\dots,n\}$. We will show that this number is equal to $n!$, which is not very hard. Start off with observing that there are $(n-1)!$ permutations of $\{1,2,3,\dots,n\}$ fixing $1$. The number is $(n-1)!$ when we fix $2$, and similarly $(n-1)!$ when we fix $n$. Hence it immediately follows that the total number of fixed points in the permutation of $\{1,2,3,\dots,n\}$ is $n(n-1)!$ which is equal to $n!$ The end. $\square$ 


(ISL 2004 C1) There are $1001$ students at an university. Some students join together to form several clubs (a student may belong to different clubs). Some clubs join together to form several societies (A club may belong to different societies) There are a total of $k$ societies. Suppose that the following conditions hold:  

  1. Each pair of students are in exactly one club. 
  2. For each student and each society, the student is in exactly one club of the society. 
  3. Each club has an odd number of students. In addition, a club with $2m + 1$ students ($m$ is a positive integer) is in exactly $m$ societies.                                                                                                                                                                Find all possible values of $k$.       

Motivation: From the above problem, it is clear that one should not be afraid to frame their own definitions in a problem. For example we defined a triple as fit in our solution. What is important to note is, that we try to count $10001k$ in two different ways. Be in the lookout for such parameters as they are the key to understand that double counting helps! 

Solution: Say an ordered triple $(a,C,S)$ to be fit if $a$ is a student, $C$ is a club and $S$ is a society such that the student is a part of the club and the club is a part of the society (in other words $a \in C$ and $C \in S$). We will compute the number of fit triples in $2$ ways.  

Firstly, for every student $a$ and society $S$, there exists a unique club $C$ such that the triplet $(a,C,S)$ is fit. Therefore there are $\boxed{10001K}$ fit ordered triples.  

Now, we count the other way around. For every club $C$, let us denote the number of members as $|C|$. By the third condition of the problem statement, $C$ is present in exactly $\frac{|C| - 1}{2}$ societies. Therefore, there are $\frac{|C|(|C| - 1)}{2}$ fit triples where the second coordinate is $C$. Now, define $\tau$ to be the set of all clubs. Therefore there are $$\sum_{C \in \tau} \frac{|C|(|C| - 2)}{2}$$ fit ordered triples. By the first condition of the problems statement, that is equal to the number of the pair of students,  which is equal to $1001 \times  5000$. Thus we get  

$$10001k = \sum_{C \in \tau} \frac{|C|(|C| - 2)}{2} = 10001 \times 5000$$  which shows that $\boxed{k = 5000}$.   


(IMO 1998 #2) In a contest there are $m$ candidates and $n$ judges, where $n \ge 3$ is an odd integer. Each candidate is evaluated by each judge as either pass or  fail. Suppose that each pair of judges agree on at most $k$ candidates. Prove that $$\frac{k}{m} \ge \frac{n-1}{2n}$$  

Motivation: In the above problem, there are two main outcomes. Pass or Fail. So the most obvious approach is to tackle the problem from the perspective of both the outcomes. That is essentially what we implement in the above solution by assuming a certain number of judges who fail the contestant and a certain number of judges who pass the contestant. This is again double counting clear as day.  

Solution:  We consider the pair of judges who agree on certain contestants. We take a look at it from $2$ perspectives. For some contestant $i$ where $i \in [1,m]$, assume that $a_i$ judges pass him and $b_i$ judges fail him. Therefore, the number of judges who pass him are: 

$$\binom{a_i}{2} + \binom{b_i}{2} = \frac{a_i^2 - a_i + b_i^2 - b_i}{2}$$ 

$$\ge \frac{(a_i + b_i)^2 \div 2}{2} - \frac{a_i + b_i}{2}$$ 

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

$$= \frac{1}{4}[(n-1)^2 - 1]$$

Since $n$ is odd and $\binom{a_i}{2} + \binom{b_i}{2}$ is an integer, the lower bound turns out to be $\frac{(n-1)^2}{4}$. 

Now we count the other way. There are $n$ judges and each of them agree on at most $k$ contestants. Therefore, the upper bound on the pair of judges that agree on a certain contestant is at most $$k \binom{n}{2}$$ Now we get the following: 

$$k \binom{n}{2} \ge \sum_{i = 1}^{m} \left(\binom{a_i}{2} + \binom{b_i}{2}\right)  \ge \frac{m(n-1)^2}{4}$$  

which upon simplification yields the desired the result. $\square$


(Italy TST) A stage course is attended by $n \ge 4$ students. The day before the final exam, each group of three students conspire against another student to throw him/her out of the exam. Prove that there is a student against whom there are at least $$\sqrt[3]{(n-1)(n-2)}$$ conspirators. 

Motivation:  Whenever you see at least or at most it is a big giveaway about the problem. Try to use pigeonhole principle in all such sort of problems and that is what we have essentially done in the above solution. We've tried to figure out the lower bound on the number of students that conspire against every student. Use pigeonhole wisely people! 

Solution: Computing the number of conspiring triples, we see that the number of conspiring triples equal to $$\binom{n}{3}  = \frac{n(n-1)(n-2)}{6}$$ Hence the conclusion that we can draw from here is that every student (say $P$) is conspired against by at least $$\frac{(n-1)(n-2)}{6}$$ triples. Since $k$ students can combine in $\binom{k}{3}$ ways. Computing $\binom{k}{3}$ gives $$\frac{k(k-1)(k-2)}{6}$$ This means that the $k$ students conspiring against $P$ must be $$\frac{(n-1)(n-2)}{6} \le \frac{k(k-1)(k-2)}{6} \le \frac{k^3}{6}$$ which implies $$k > \sqrt[3]{(n-1)(n-2)}$$ which is the desired result. $\square$ 


(All Russian 1996) In the duma there are $1600$ delegates, who have formed $16000$ committees of $80$ people each. Prove that one can find $2$ committees having no fewer than $4$ common members.  

Solution: Let $P$ be the number of triples. Now assume that every committee has $\le 3$ people in common. Let $P$ be the number of triples $(i , a_1 , a_2)$ where the person $i$ is the part of $a_1$ and $a_2$. Suppose $i$ is in $c_i$ committees. Then we have the following: 

$$P = \sum_{i = 1}^{1600} \binom{c_i}{2} \ge 1600 \binom{\frac{\sum_{i = 1}^{1600}c_i}{1600}}{2} = 1600 \binom{\frac{80 \times 16000}{1600}}{2} = 1600 \binom{800}{2}$$

Choose $a_1$ and $a_2$ in $\binom{16000}{2}$ ways. Since they have at most $3$ people in common $$ P \le 3 \binom{16000}{2}$$ However $1600 \binom{800}{2} > 3\binom{16000}{2}$ which gives us a contradiction.  

Comments: This problem was nothing more than careful (and messy) computation. The main observation is to first compute the number of committees a person $k$ belongs to and the rest of the problem boils down to computing binomial coefficients and using inequalities to get the desired result. There is also a way to tackle this problem using the concept of expected value but that's beyond the scope of this post.  


(IMO 1989 #3) Let $n$ and $k$ be positive integers and let $S$ be a set of $n$ points in the plane such that  

  1. No three points of $S$ are collinear. 
  2. For every point $P$ of $S$ there are at least $k$ points of $S$ equidistant from $P$. Prove that $$k < \frac{1}{2} + \sqrt{2n}$$

Motivation: "Equidistant" from $P$ actually hints at the construction of a circle. But before we dive into that it is important that we modify the inequality a bit. That's what we have done in the solution by getting rid of the square roots and hence making the inequality neater and easier to work with. Taking note of the fact that there is at least $1$ common chord, we come up with the fact that there are $\binom{n}{2}$ chords when counted twice. The rest being boiled down to manipulation and inequality.     

Solution: Our first goal here is to manipulate the inequality to something "neat". Interestingly, we can convert the inequality in terms of $n$ as follows $$n > \frac{k(k-1)}{2} + \frac{1}{8}$$ Since both $n$ and $k$ are positive integers, we can further manipulate the inequality to $$(n-1) \ge \binom{k}{2}$$ We now count the number of edges by joining any two vertices of $S$ by an edge. We employ double counting.  

On one hand we have $\binom{n}{2}$ edges. On the other hand, from any point of $S$, there are at least $k$ points that are equidistant from it.  Therefore, if we draw a circle with the point as center and the distance as radius, then there are at least $\binom{k}{2}$ chords that are edges. The total number of such chords (counted with multiplicities) is at least equal to $n \binom{k}{2}$ Any $2$ circles can have at least $1$ common chord and hence, there are at most $\binom{n}{2}$ chords counted twice. Therefore we get the following $$n \binom{k}{2} - \binom{n}{2} \le \binom{n}{2}$$ which upon simplification, gives $$(n-1) \ge \binom{k}{2}$$ which is the desired inequality that we had to prove. $\square$  

Comments

Popular posts from this blog

Constructions in Number Theory

Hi, I am Emon, a ninth grader, an olympiad aspirant, hailing from Kolkata. I love to do olympiad maths and do some competitive programming in my leisure hours, though I take it seriously. I had written INOI this year. Today, I would be giving you a few ideas on how to Construct in Number Theory . Well, so we shall start from the basics and shall try to dig deeper into it with the help of some important and well-known theorems and perhaps, some fancy ones as well. Okay, so without further delay, let's start off... What do we mean by "Constructions"? If noticed, you can see that you often face with some problems in olympiad saying, "... Prove that there exists infinitely many numbers satisfying the given conditions" or "... Prove that there exists a number satisfying the above conditions." These are usually the construction-problems .  For example, let's consider a trivial example : Problem. Prove that there exist infinitely many integers $a$ such th

EGMO solutions, motivations and reviews ft. Atul, Pranjal and Abhay

The  European Girls' Mathematical Olympiad a.k.a EGMO 2022 just ended. Congrats to Jessica Wan from USA, Taisiia Korotchenko, and Galiia Sharafetdinova for the perfect scores! Moreover, the Indian girls brought home 4 bronze medals! By far, this is the best result the EGMO India Team has ever achieved! To celebrate the brilliant result, here's a compilation of EGMO 2022 solutions and motivations written by my and everyone's favorite IMOTCer Atul ! And along with that, we also have reviews of each problem written by everyone's favorite senior, Pranjal !  These solutions were actually found by Atul, Pranjal,  and Abhay  during the 3-hour live solve. In the live solve, they solved all the 6 problems in 3 hours 😍!!! Okie Dokie, I think we should get started with the problems! Enjoy! Problem 1:  Let $ABC$ be an acute-angled triangle in which $BC<AB$ and $BC<CA$. Let point $P$ lie on segment $AB$ and point $Q$ lie on segment $AC$ such that $P \neq B$, $Q \neq C$ and

Q&A with experts about bashing

Heyy everyone! From the title, you can see that we are going to talk about  BASH.  Yesss, we are going to discuss whether you really need to learn bash or not?  Let me first introduce myself, I am Pranav Choudhary, a 10th grader from Haryana(India). I like to do geo and combo the most :PP. Oki so let's begin! For those of you who don't know what bashing is, lemme give you a brief introduction first. Bashing is basically a technique used to solve Geometry Problems. In general, when you try a geo problem you might think of angles, similarities, and some other techniques (e.g. Inversion, spiral similarity etc). All of which are called synthetic geometry. But sometimes people use various other techniques called "bash" to solve the same problems.  Now there are different kinds of bashing techniques, e.g. - Coordinate bash, Trig Bash, Complex bash, Barycentric Coordinates. Let me give you a brief introduction to each of them.  Coordinate Bash : You set one point as the orig