Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

For a pair (A,B) of subsets of the set X={1,2,3,...,100}, let A*B denote the set of all elements of X which belong to exactly one of A or B. What is the number of pairs (A,B) of subsets of X such that A*B={2,4,...,100}?

share|cite|improve this question
The operation "*" is known as the symmetric difference, and usually denoted by $\triangle$. – Yuval Filmus Apr 20 '11 at 6:52
up vote 4 down vote accepted

Hint: What can you say about each element in $A\triangle B$? What can you say about each element not in $A\triangle B$?

share|cite|improve this answer
Yes, it's just a difference in notation, but how to count? I never came across this sort of operation earlier. – Bhaskar Dey Apr 20 '11 at 6:59
There is no involved counting necessary here. The essential point is to s e e what kind of pairs $A$, $B$ are possible under the given constraint. – Christian Blatter Apr 20 '11 at 8:08
I think we're being too subtle. Five hours, and no one (but me) has upvoted your answer, and no one at all has upvoted mine. – Gerry Myerson Apr 20 '11 at 13:09
@Bhaskar: to follow up on Yuval and Gerry-If $1 \in A$, is $1 \in B$? If $2 \in A$, is $2 \in B$? – Ross Millikan Apr 20 '11 at 13:51
@Gerry Five hours does not seem much. And I like waaaay more your hints and Yuval's and Ross's than the flat answers given to obvious homework questions too often on this site. – Did Apr 21 '11 at 7:58

Different hint: given $A$, how many different possibilities are there for $B$?

share|cite|improve this answer
I like your hint better. – Yuval Filmus Apr 20 '11 at 15:45

Yet another hint: show that the set of all subsets of $X$ forms a group under symmetric difference, then note that you're asking how many times a given group element shows up in the group table.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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