2
$\begingroup$

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
    The operation "*" is known as the symmetric difference, and usually denoted by $\triangle$.2011-04-20

3 Answers 3

4

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

  • 0
    Yes, it's just a difference in notation, but how to count? I never came across this sort of operation earlier.2011-04-20
  • 0
    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.2011-04-20
  • 0
    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.2011-04-20
  • 0
    @Bhaskar: to follow up on Yuval and Gerry-If $1 \in A$, is $1 \in B$? If $2 \in A$, is $2 \in B$?2011-04-20
  • 0
    @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.2011-04-21
4

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

  • 0
    I like your hint better.2011-04-20
2

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.