MHB How many subsets of set A satisfy given conditions?

  • Thread starter Thread starter Evgeny.Makarov
  • Start date Start date
  • Tags Tags
    Finite Sets
AI Thread Summary
The discussion revolves around a combinatorial problem involving set theory, specifically focusing on the subsets of set A under certain conditions. Key conditions include the sizes of sets B and C, as well as their intersections and differences. The problem asks for the number of subsets X that meet specific criteria related to intersections with B and C and the size of the set difference from B and C. The difficulty of the problem is debated, with opinions suggesting it is suitable for college freshmen or even secondary school students. Overall, the problem is considered a standard exercise in algebra or pre-calculus.
Evgeny.Makarov
Gold Member
MHB
Messages
2,434
Reaction score
4
Consider a set $A$ and its subsets $B$ and $C$. It is known that $|A-(B\cap C)|=8$, $|B|=5$, $|C-B|=1$ and $|B\cap C|=3$ (here $-$ denotes set difference). How many subsets $X\subseteq A$ are there if $X\cap B\cap C\ne\emptyset$, $|X-(B\cup C)|\ge3$ and $|X\cap (B-C)|=2$?
 
Mathematics news on Phys.org
Since nobody gave an answer, I am posting a solution.

I will omit $\cap$ and write intersection as multiplication. I will also write $\sqcup$ for disjoint union.

In this problem $A$ is the universal set, and each element of $A$ belongs to exactly one of four classes: it can fall in or outside $B$ and $C$. Since $A-BC=\overline{BC}=\overline{B}\cup\overline{C}=\overline{B}C\sqcup B\overline{C}\sqcup\overline{B}\overline{C}$, $B=BC\sqcup B\overline{C}$ and $C-B=\overline{B}C$, we have the following system of equations.
\begin{align*}
|\overline{B}C|+|B\overline{C}|+|\overline{B}\overline{C}|&=8\\
|BC|+|B\overline{C}|&=5\\
|\bar{B}C|&=1\\
|BC|&=3
\end{align*}
Solving this system, we can fill the following table form of the Venn diagram.
\begin{tikzpicture}[scale=1.3,y={(0cm,-1cm)}]
\draw[step=1cm] (-.3,-.3) grid (2,2);
\node[above] at (.5,0) {$B$};
\node[above] at (1.5,0) {$\overline{B}$};
\node
at (0,.5) {$C$};
\node
at (0,1.5) {$\overline{C}$};
\path[shift={(.5,.5)}] (0,0) node {3} (1,0) node {1} (0,1) node {2} (1,1) node {5};
\end{tikzpicture}

Set \(X\) is also split into four disjoint classes. The condition $XBC\ne\emptyset$ gives us $2^3-1=7$ variants for $XBC$. The condition $|X-(B\cup C)|\ge3$ means that $X\overline{B}\overline{C}$ can be chosen in $\binom{5}{3}+\binom{5}{4}+\binom{5}{5}=16$ ways. The condition $|X(B-C)|=|XB\overline{C}|=2$ requires that both elements of $B\overline{C}$ are included in $X$. Finally, the problem does not say anything about $X\overline{B}C$, which gives us two variants: the only element of $\overline{B}C$ may or may not be in $X$. Altogether, there are $7\cdot16\cdot2=224$ variants for $X$.​


I would appreciate your opinion on the difficulty level of this problem. Which year in the university is it appropriate for?​
 
That looks like a fairly standard algebra or pre-calculus problem. I wouldn't be surprised to see it in a college freshman or even secondary school class.
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Is it possible to arrange six pencils such that each one touches the other five? If so, how? This is an adaption of a Martin Gardner puzzle only I changed it from cigarettes to pencils and left out the clues because PF folks don’t need clues. From the book “My Best Mathematical and Logic Puzzles”. Dover, 1994.
Back
Top