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\}?$

  • 2
    $\begingroup$ The operation "*" is known as the symmetric difference, and usually denoted by $\triangle$. $\endgroup$ – 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$?

  • $\begingroup$ Yes, it's just a difference in notation, but how to count? I never came across this sort of operation earlier. $\endgroup$ – Bhaskar Dey Apr 20 '11 at 6:59
  • $\begingroup$ 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. $\endgroup$ – Christian Blatter Apr 20 '11 at 8:08
  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson Apr 20 '11 at 13:09
  • $\begingroup$ @Bhaskar: to follow up on Yuval and Gerry-If $1 \in A$, is $1 \in B$? If $2 \in A$, is $2 \in B$? $\endgroup$ – Ross Millikan Apr 20 '11 at 13:51
  • $\begingroup$ @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. $\endgroup$ – Did Apr 21 '11 at 7:58

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

  • $\begingroup$ I like your hint better. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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