# How to count number of pairs of subsets $(A,B)$ of $X=\{1,2,..,100\}$ under the given constraint?

For a pair $(A,B)$ of subsets of the set $X=\{1,2,3,...,100\}$, let $A\Delta 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\Delta B=\{2,4,...,100\}?$

• The operation "*" is known as the symmetric difference, and usually denoted by $\triangle$. – Yuval Filmus Apr 20 '11 at 6:52

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

• 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$?

• 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.