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?
3
$\begingroup$
combinatorics
-
2The operation "*" is known as the symmetric difference, and usually denoted by $\triangle$. – 2011-04-20
3 Answers
5
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@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.