In combinatorics, why is asking the opposite problem often times easier?

Question

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?

It doesn't just apply to combinatorics, it applies to life in general. — Théophile, Aug 02 '18 at 02:31
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. — poyea, Aug 02 '18 at 03:43
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. — Q the Platypus, Aug 02 '18 at 03:55
For every problem, there are two possibilities: either the problem is easier, or its opposite is easier. So it should occur half the time :) — Carmeister, Aug 02 '18 at 07:20

Q the Platypus · Accepted Answer · 2018-08-02T22:52:24.510

34

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.

edited Aug 02 '18 at 22:52

answered Aug 02 '18 at 04:11

Q the Platypus

4,626

4

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. – Todd Wilcox Aug 02 '18 at 19:40
more generally then (beyond just combinatorics), wherever we have De Morgan's laws applicable, we can consider whether transforming the problem into the alternate variant is easier? i feel like i have come across such instances before, but i can't easily recall... – bzm3r Aug 02 '18 at 19:41
8

Is “combotronics” a word or just a typo? Either way, I like how it sounds! :) – Aug 02 '18 at 20:26
1

@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 . – Q the Platypus Aug 02 '18 at 22:59
4

@kkm yes it’s a typo. Not my best sounding typo either which would be infostructure. – Q the Platypus Aug 02 '18 at 23:01
I like infostructure too! :) – Aug 02 '18 at 23:38
Look at a Venn diagram. "And" is just one section of the chart. "Or" is three. – Dan Aug 02 '18 at 23:39
2

I'm actually a little disappointed the typo was corrected... – silvascientist Aug 03 '18 at 05:17

score 18 · Answer 2 · answered Aug 02 '18 at 02:53

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.

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. — user3067860, Aug 02 '18 at 14:52

Martin Roberts · Answer 3 · 2018-08-03T06:59:27.663

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:

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) — Jesus is Lord, Aug 02 '18 at 19:58

score 3 · Answer 4 · answered Aug 02 '18 at 03:10

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.

score 1 · Answer 5 · answered Aug 02 '18 at 03:31

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.

In combinatorics, why is asking the opposite problem often times easier?

5 Answers5

Linked