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\}?$
How to count number of pairs of subsets $(A,B)$ of $ X=\{1,2,..,100\}$ under the given constraint?
2
$\begingroup$
combinatorics
-
2The operation "*" is known as the symmetric difference, and usually denoted by $\triangle$. – 2011-04-20
3 Answers
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$?
-
0Yes, it's just a difference in notation, but how to count? I never came across this sort of operation earlier. – 2011-04-20
-
0There 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
-
0I 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$?
-
0I 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.