17
$\begingroup$

Consider the birthday problem. Given $N$ people, how many ways are there for there to exist some pair of people with the same birthday?

Enumerating the possibilities quickly becomes tedious

However, the complement problem (Given $N$ people, how many ways are there for no one to have the same birthday?) is trivial.

In fields like probability, this has obvious applications, due to the "complement law":

if $A \cup A^c = S$, where $S$ is the entire sample space, then $$P(A) + P(A^c) = 1 \implies P(A) = 1 - P(A^c)$$

In general, this pattern is very common. Intuitively, I sense:

  • somehow, the complement problem is asking for a lot less information

  • if one has something like the "complement law" in probability, then in some restricted scope of problems, the "complement law" gives in some sense, the "same amount of information"

What do mathematicians call what I am getting at here? Am I overblowing how common a trend it is?

$\endgroup$
  • 14
    $\begingroup$ It doesn't just apply to combinatorics, it applies to life in general. $\endgroup$ – Théophile Aug 2 '18 at 2:31
  • 1
    $\begingroup$ I call it, "Not seeing the forest for the trees." $\endgroup$ – saulspatz Aug 2 '18 at 2:57
  • 1
    $\begingroup$ Some questions are just set to be easily solved from the opposite. I think that's just "thinking outside the box" in the context of probability theory. $\endgroup$ – poyea Aug 2 '18 at 3:43
  • 3
    $\begingroup$ This is common in other places in mathmatics. For example when creating a proof it is often easier to prove the opposite thing is false, then proving something directly is true. $\endgroup$ – Q the Platypus Aug 2 '18 at 3:55
  • 4
    $\begingroup$ For every problem, there are two possibilities: either the problem is easier, or its opposite is easier. So it should occur half the time :) $\endgroup$ – Carmeister Aug 2 '18 at 7:20
34
$\begingroup$

In combinatorics answering “and” style questions is easy because it is a multiplication. This is easy since you can remove common factors between denominators and numerators, and use the binomial/choice function. Also any time a 1 or 0 comes up the operation becomes trivial.

However asking "or" style questions is difficult since you have to add the numbers and then work out where you have a double count and subtract them.

De Morgan's laws $\neg ( a \vee b) = ( \neg a \wedge \neg b)$ allows you to transform a “or” problem into a “not and” problem which is easier.

| cite | improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ It might enhance this answer to mention that one of the things that makes multiplying "easier" is that often there are terms in a denominator that can be canceled with terms in one or more numerators. I know multiplication is easier than addition in other ways, but I'm not sure how to explain why. $\endgroup$ – Todd Wilcox Aug 2 '18 at 19:40
  • 7
    $\begingroup$ Is “combotronics” a word or just a typo? Either way, I like how it sounds! :) $\endgroup$ – user22961 Aug 2 '18 at 20:26
  • 1
    $\begingroup$ @user89 Yes. One of the things the things you get is that you can transform a “for all x P(x) is true” into “(there exists an x where P(x) is false) is false” which is often easier . $\endgroup$ – Q the Platypus Aug 2 '18 at 22:59
  • 3
    $\begingroup$ @kkm yes it’s a typo. Not my best sounding typo either which would be infostructure. $\endgroup$ – Q the Platypus Aug 2 '18 at 23:01
  • 1
    $\begingroup$ I'm actually a little disappointed the typo was corrected... $\endgroup$ – silvascientist Aug 3 '18 at 5:17
17
$\begingroup$

Put it this way: for every problem, there are two equivalent ways to put it, with each way being a simple complement of the other. There may be a disparity: one is significantly simpler than the other. But, they are both immediately equivalent; you can ask either question in place of the other.

So then, the issue becomes, why are people choosing to pose to you the less simple problem? I think the reason is probably pedagogical: looking at the complement problem is an effort-inexpensive but extremely valuable tool for solving combinatorial problems. It's a lesson worth learning that it's worth looking at the complement problem, right off the bat, to see if it's any easier.

There might potentially be some deeper reasons, possibly about some correlation between the harder of the two problems having superior aesthetics most of the time, but this kind of question is not exactly the wheelhouse of a mere mathematician such as myself.

| cite | improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ The times when the complement is more optimal may be more memorable than times when the naive solution is optimal, too...especially if you spent more time per problem like that compared to problems where the answer was straightforward. $\endgroup$ – user3067860 Aug 2 '18 at 14:52
6
$\begingroup$

You have basically answered this, in your dot points.

I would articulate it as follows:

Answering the complementary version of a combinatorics question is often easier if the original question contains (directly or indirectly) the constraint "at least one".

In such cases, obtaining the answer typically requires enumerating over a very large number of combinations, whereas the complementary version only contains a small number of possibilities to enumerate and thus is more amenable to direct calculation.

For example, in the birthday problem, can be worded as, "Given $N$ people, what is the likelihood that at least one pair of people have a common birthday"

The complementary version is "Given $N$ people, what is the likelihood that exactly zero people have a common birthday?"

Other math stackexchange questions where you can see this phenomenon:

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I assume I'm missing something: Wouldn't the complement for "at least k" = (exactly k, k+1, ..., or n) be "at most k-1" = (exactly 2, 3, ..., or k-1)? (It doesn't make sense for 0 or 1 people to have a birthday in common, so start at 2) $\endgroup$ – Jared Aug 2 '18 at 19:58
  • $\begingroup$ Edited to make it clearer. $\endgroup$ – Martin Roberts Aug 3 '18 at 6:51
3
$\begingroup$

In combinatorics when we know total number of all possibilities and counting the number of possibilities satisfying condition C or violating it are equivalent problems. That is knowing one you get the other by simple subtraction from the other known number.

Many times to count the possibilities satisfying condition C, may be difficult directly. If C can be broken up into disjoint possibilities you count in each of the cases and add them up.

SO it boils down to whether the condition C or its negation (complement) has more cases. Choose the one involving fewer cases. In an experiment invovling counting how many results in throwing 10 coins produce at least 2 heads the possibilities 2 heads, 3 heads, and so on up to 10 heads. However the complement is 0 heads or 1 heads.

Clear that the second one is easy.

The key point is how many cases (mutually exclusive or disjoint) you have to analyze. This will tell you which is is easier original problem or the complementary problem.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

The set of all possible combinatorics problems is symmetric w.r.t. taking the complement. But the problems we encounter are not randomly chosen from such a set, usually these problems are kooked up problems that are challenging enough to be interesting but they are also solvable. A large class of such problems are problems that simplify when taking the complement.

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.