1
$\begingroup$

Compute the number of subsets of set $A=\{1,2,\ldots,11\}$ that contain the same number of even and odd values, e.g. the subsets $\varnothing, \{1,2,5,8\}$ and $\{3,5,8,10\}$ should be counted, while $\{1,2,3\}$, $\{1,3,5,6\}$ and $\{1,2,\ldots,11\}$ shouldn’t.

I got $462$, but I don't know if that is the correct answer.

The way I did it is that I made two subsets: one containing all the odd numbers and one containing all the even numbers. Then, I tried to find the possible combinations that will result in $0, 2,\ldots10$ elements and added them, giving me $462$.

$\endgroup$
  • $\begingroup$ The number $462$ is correct. $\endgroup$ – André Nicolas Nov 9 '13 at 8:14
  • 1
    $\begingroup$ I dont see anything wrong with your answer $\endgroup$ – Arief Anbiya Nov 9 '13 at 8:16
1
$\begingroup$

$$\{1,3,5,7,9,11\},\{2,4,6,8,10\}$$ $$\binom{6}{0}\binom{5}{0}+\binom{6}{1}\binom{5}{1}+\binom{6}{2}\binom{5}{2}+\binom{6}{3}\binom{5}{3}+\binom{6}{4}\binom{5}{4}+\binom{6}{5}\binom{5}{5}=$$ $$=1+30+150+200+75+6=462$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Hello dera friend. :+) $\endgroup$ – mrs Nov 9 '13 at 14:10
0
$\begingroup$

Here is a slick but rather non-obvious way to solve the problem with less arithmetic. Suppose that $S$ is a subset of $A=\{1,2,\ldots,11\}$ with the same number of even and odd elements. Let

$$S^*=\{k\in S:k\text{ is even}\}\cup\{k\in A\setminus S:k\text{ is odd}\}\;.$$

In other words, $S^*$ is formed from $S$ by replacing the odd numbers in $S$ with the odd numbers that aren’t in $S$, while leaving the even numbers alone. The map $S\mapsto S^*$ is a bijection from $\wp(A)$ to itself, as may be seen by observing that it is its own inverse: $S^{**}=S$ for each $S\subseteq A$.

Let $\mathscr{E}$ be the collection of $S\subseteq A$ with the same number of even and odd elements, and let $\mathscr{E}^*=\{S^*:S\in\mathscr{E}\}$; $|\mathscr{E}|=|\mathscr{E}^*|$, so we’ll be done if we can count the sets in $\mathscr{E}$.

For $S\subseteq A$ let $e(S)$ be the number of even elements of $S$ and $o(S)$ the number of odd elements of $S$; $o(A)=6$, so $e(S^*)=e(S)$, and $o(S^*)=6-o(S)$. If $S\in\mathscr{E}$, then $e(S)=o(S)$, so $e(S^*)+o(S^*)=e(S)+6-o(S)=6$. Thus, $e(S)+o(S)=6$ for every $S\in\mathscr{E}^*$. Conversely, if $S\subseteq A$, and $e(S)+o(S)=6$, then $o(S^*)=6-o(S)=e(S)=e(S^*)$, so $S^*\in\mathscr{E}$, and therefore $S\in\mathscr{E}^*$. In short,

$$\mathscr{E}^*=\{S\subseteq A:e(S)+o(S)=6\}=\{S\subseteq A:|A|=6\}\;,$$

and therefore $$|\mathscr{E}|=|\mathscr{E}^*|=\binom{11}6=462\;.$$

(Writing it up carefully makes it look harder than it really is!)

| cite | improve this answer | |
$\endgroup$

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.