Mixing
In combinatorics, why is asking the opposite problem often times easier? [on hold]
Clash Royale CLAN TAG#URR8PPP
up vote
16
down vote
favorite
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?
combinatorics
edited Aug 2 at 8:13
Lorenzo B.
1,5402318
asked Aug 2 at 2:28
user89
5341546
put on hold as too broad by m_t_, Isaac Browne, Henrik, max_zorn, Lord Shark the Unknown Aug 3 at 8:12
Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
 |Â
show 2 more comments
up vote
16
down vote
favorite
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?
combinatorics
edited Aug 2 at 8:13
Lorenzo B.
1,5402318
asked Aug 2 at 2:28
user89
5341546
put on hold as too broad by m_t_, Isaac Browne, Henrik, max_zorn, Lord Shark the Unknown Aug 3 at 8:12
Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
13
It doesn't just apply to combinatorics, it applies to life in general.
– Théophile
Aug 2 at 2:31
I call it, "Not seeing the forest for the trees."
– saulspatz
Aug 2 at 2:57
1
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 2 at 3:43
3
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 2 at 3:55
3
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 2 at 7:20
 |Â
show 2 more comments
up vote
16
down vote
favorite
up vote
16
down vote
favorite
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?
combinatorics
edited Aug 2 at 8:13
Lorenzo B.
1,5402318
asked Aug 2 at 2:28
user89
5341546
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?
combinatorics
edited Aug 2 at 8:13
Lorenzo B.
1,5402318
asked Aug 2 at 2:28
user89
5341546
edited Aug 2 at 8:13
Lorenzo B.
1,5402318
edited Aug 2 at 8:13
Lorenzo B.
1,5402318
edited Aug 2 at 8:13
Lorenzo B.
1,5402318
1,5402318
asked Aug 2 at 2:28
user89
5341546
asked Aug 2 at 2:28
user89
5341546
asked Aug 2 at 2:28
user89
5341546
5341546
put on hold as too broad by m_t_, Isaac Browne, Henrik, max_zorn, Lord Shark the Unknown Aug 3 at 8:12
Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
put on hold as too broad by m_t_, Isaac Browne, Henrik, max_zorn, Lord Shark the Unknown Aug 3 at 8:12
Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
13
It doesn't just apply to combinatorics, it applies to life in general.
– Théophile
Aug 2 at 2:31
I call it, "Not seeing the forest for the trees."
– saulspatz
Aug 2 at 2:57
1
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 2 at 3:43
3
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 2 at 3:55
3
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 2 at 7:20
 |Â
show 2 more comments
13
It doesn't just apply to combinatorics, it applies to life in general.
– Théophile
Aug 2 at 2:31
I call it, "Not seeing the forest for the trees."
– saulspatz
Aug 2 at 2:57
1
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 2 at 3:43
3
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 2 at 3:55
3
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 2 at 7:20
13
13
It doesn't just apply to combinatorics, it applies to life in general.
– Théophile
Aug 2 at 2:31
It doesn't just apply to combinatorics, it applies to life in general.
– Théophile
Aug 2 at 2:31
I call it, "Not seeing the forest for the trees."
– saulspatz
Aug 2 at 2:57
I call it, "Not seeing the forest for the trees."
– saulspatz
Aug 2 at 2:57
1
1
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 2 at 3:43
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 2 at 3:43
3
3
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 2 at 3:55
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 2 at 3:55
3
3
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 2 at 7:20
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 2 at 7:20
 |Â
show 2 more comments
5 Answers
5
active
oldest
votes
up vote
33
down vote
accepted
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.
answered Aug 2 at 4:11
Q the Platypus
2,998831
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 2 at 19:40
7
Is “combotronics†a word or just a typo? Either way, I like how it sounds! :)
– kkm
Aug 2 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 2 at 22:59
3
@kkm yes it’s a typo. Not my best sounding typo either which would be infostructure.
– Q the Platypus
Aug 2 at 23:01
1
I'm actually a little disappointed the typo was corrected...
– Monstrous Moonshiner
Aug 3 at 5:17
 |Â
show 3 more comments
up vote
16
down vote
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.
answered Aug 2 at 2:53
Theo Bendit
11.7k1841
4
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 2 at 14:52
add a comment |Â
up vote
7
down vote
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:
How many combinations contain at least two As
Combinations of pizza toppings with at least one vegetable and at least one meat.
Combinations including "at most"
answered Aug 2 at 2:59
Martin Roberts
1,204318
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)
– Words Like Jared
Aug 2 at 19:58
Edited to make it clearer.
– Martin Roberts
Aug 3 at 6:51
add a comment |Â
up vote
4
down vote
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.
answered Aug 2 at 3:10
P Vanchinathan
13.9k12035
add a comment |Â
up vote
1
down vote
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.
answered Aug 2 at 3:31
Count Iblis
7,92121332
add a comment |Â
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
33
down vote
accepted
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.
answered Aug 2 at 4:11
Q the Platypus
2,998831
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 2 at 19:40
7
Is “combotronics†a word or just a typo? Either way, I like how it sounds! :)
– kkm
Aug 2 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 2 at 22:59
3
@kkm yes it’s a typo. Not my best sounding typo either which would be infostructure.
– Q the Platypus
Aug 2 at 23:01
1
I'm actually a little disappointed the typo was corrected...
– Monstrous Moonshiner
Aug 3 at 5:17
 |Â
show 3 more comments
up vote
33
down vote
accepted
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.
answered Aug 2 at 4:11
Q the Platypus
2,998831
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 2 at 19:40
7
Is “combotronics†a word or just a typo? Either way, I like how it sounds! :)
– kkm
Aug 2 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 2 at 22:59
3
@kkm yes it’s a typo. Not my best sounding typo either which would be infostructure.
– Q the Platypus
Aug 2 at 23:01
1
I'm actually a little disappointed the typo was corrected...
– Monstrous Moonshiner
Aug 3 at 5:17
 |Â
show 3 more comments
up vote
33
down vote
accepted
up vote
33
down vote
accepted
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.
answered Aug 2 at 4:11
Q the Platypus
2,998831
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.
answered Aug 2 at 4:11
Q the Platypus
2,998831
edited Aug 2 at 22:52
answered Aug 2 at 4:11
Q the Platypus
2,998831
answered Aug 2 at 4:11
Q the Platypus
2,998831
answered Aug 2 at 4:11
Q the Platypus
2,998831
2,998831
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 2 at 19:40
7
Is “combotronics†a word or just a typo? Either way, I like how it sounds! :)
– kkm
Aug 2 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 2 at 22:59
3
@kkm yes it’s a typo. Not my best sounding typo either which would be infostructure.
– Q the Platypus
Aug 2 at 23:01
1
I'm actually a little disappointed the typo was corrected...
– Monstrous Moonshiner
Aug 3 at 5:17
 |Â
show 3 more comments
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 2 at 19:40
7
Is “combotronics†a word or just a typo? Either way, I like how it sounds! :)
– kkm
Aug 2 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 2 at 22:59
3
@kkm yes it’s a typo. Not my best sounding typo either which would be infostructure.
– Q the Platypus
Aug 2 at 23:01
1
I'm actually a little disappointed the typo was corrected...
– Monstrous Moonshiner
Aug 3 at 5:17
4
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 2 at 19:40
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 2 at 19:40
7
7
Is “combotronics†a word or just a typo? Either way, I like how it sounds! :)
– kkm
Aug 2 at 20:26
Is “combotronics†a word or just a typo? Either way, I like how it sounds! :)
– kkm
Aug 2 at 20:26
1
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 2 at 22:59
@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 2 at 22:59
3
3
@kkm yes it’s a typo. Not my best sounding typo either which would be infostructure.
– Q the Platypus
Aug 2 at 23:01
@kkm yes it’s a typo. Not my best sounding typo either which would be infostructure.
– Q the Platypus
Aug 2 at 23:01
1
1
I'm actually a little disappointed the typo was corrected...
– Monstrous Moonshiner
Aug 3 at 5:17
I'm actually a little disappointed the typo was corrected...
– Monstrous Moonshiner
Aug 3 at 5:17
 |Â
show 3 more comments
up vote
16
down vote
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.
answered Aug 2 at 2:53
Theo Bendit
11.7k1841
4
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 2 at 14:52
add a comment |Â
up vote
16
down vote
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.
answered Aug 2 at 2:53
Theo Bendit
11.7k1841
4
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 2 at 14:52
add a comment |Â
up vote
16
down vote
up vote
16
down vote
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.
answered Aug 2 at 2:53
Theo Bendit
11.7k1841
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.
answered Aug 2 at 2:53
Theo Bendit
11.7k1841
answered Aug 2 at 2:53
Theo Bendit
11.7k1841
answered Aug 2 at 2:53
Theo Bendit
11.7k1841
answered Aug 2 at 2:53
Theo Bendit
11.7k1841
11.7k1841
4
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 2 at 14:52
add a comment |Â
4
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 2 at 14:52
4
4
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 2 at 14:52
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 2 at 14:52
add a comment |Â
up vote
7
down vote
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:
How many combinations contain at least two As
Combinations of pizza toppings with at least one vegetable and at least one meat.
Combinations including "at most"
answered Aug 2 at 2:59
Martin Roberts
1,204318
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)
– Words Like Jared
Aug 2 at 19:58
Edited to make it clearer.
– Martin Roberts
Aug 3 at 6:51
add a comment |Â
up vote
7
down vote
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:
How many combinations contain at least two As
Combinations of pizza toppings with at least one vegetable and at least one meat.
Combinations including "at most"
answered Aug 2 at 2:59
Martin Roberts
1,204318
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)
– Words Like Jared
Aug 2 at 19:58
Edited to make it clearer.
– Martin Roberts
Aug 3 at 6:51
add a comment |Â
up vote
7
down vote
up vote
7
down vote
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:
How many combinations contain at least two As
Combinations of pizza toppings with at least one vegetable and at least one meat.
Combinations including "at most"
answered Aug 2 at 2:59
Martin Roberts
1,204318
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:
How many combinations contain at least two As
Combinations of pizza toppings with at least one vegetable and at least one meat.
Combinations including "at most"
answered Aug 2 at 2:59
Martin Roberts
1,204318
edited Aug 3 at 6:59
answered Aug 2 at 2:59
Martin Roberts
1,204318
answered Aug 2 at 2:59
Martin Roberts
1,204318
answered Aug 2 at 2:59
Martin Roberts
1,204318
1,204318
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)
– Words Like Jared
Aug 2 at 19:58
Edited to make it clearer.
– Martin Roberts
Aug 3 at 6:51
add a comment |Â
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)
– Words Like Jared
Aug 2 at 19:58
Edited to make it clearer.
– Martin Roberts
Aug 3 at 6:51
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)
– Words Like Jared
Aug 2 at 19:58
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)
– Words Like Jared
Aug 2 at 19:58
Edited to make it clearer.
– Martin Roberts
Aug 3 at 6:51
Edited to make it clearer.
– Martin Roberts
Aug 3 at 6:51
add a comment |Â
up vote
4
down vote
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.
answered Aug 2 at 3:10
P Vanchinathan
13.9k12035
add a comment |Â
up vote
4
down vote
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.
answered Aug 2 at 3:10
P Vanchinathan
13.9k12035
add a comment |Â
up vote
4
down vote
up vote
4
down vote
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.
answered Aug 2 at 3:10
P Vanchinathan
13.9k12035
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.
answered Aug 2 at 3:10
P Vanchinathan
13.9k12035
answered Aug 2 at 3:10
P Vanchinathan
13.9k12035
answered Aug 2 at 3:10
P Vanchinathan
13.9k12035
answered Aug 2 at 3:10
P Vanchinathan
13.9k12035
13.9k12035
add a comment |Â
add a comment |Â
up vote
1
down vote
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.
answered Aug 2 at 3:31
Count Iblis
7,92121332
add a comment |Â
up vote
1
down vote
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.
answered Aug 2 at 3:31
Count Iblis
7,92121332
add a comment |Â
up vote
1
down vote
up vote
1
down vote
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.
answered Aug 2 at 3:31
Count Iblis
7,92121332
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.
answered Aug 2 at 3:31
Count Iblis
7,92121332
answered Aug 2 at 3:31
Count Iblis
7,92121332
answered Aug 2 at 3:31
Count Iblis
7,92121332
answered Aug 2 at 3:31
Count Iblis
7,92121332
7,92121332
add a comment |Â
add a comment |Â
13
It doesn't just apply to combinatorics, it applies to life in general.
– Théophile
Aug 2 at 2:31
I call it, "Not seeing the forest for the trees."
– saulspatz
Aug 2 at 2:57
1
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 2 at 3:43
3
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 2 at 3:55
3
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 2 at 7:20