2.4 Cardinal d’un conjunt

Exercici 2.42.

Sigui $E$ un conjunt referencial i considerem dos conjunts finits $A$ i $B$ . Demostra les següents propietats: (a) Si $A\subset B$ , llavors $\#A\leq$ $\#B$ ; (b) $\#\left(A\cup B\right)=$ $\#A+$ $\#B-$ $\#\left(A\cap B\right)$ ; (c) $\#\left(A\cup B\cup C\right)=$ $\#A+$ $\#B+$ $\#C-$ $\#\left(A\cap B\right)-$ $\#\left(A\cap C\right)-$ $\#\left(B\cap C\right)+$ $\#\left(A\cap B\cap C\right)$ ; (d) $\#\complement A=$ $\#E-$ $\#A$ ; (e) $\#\left(A\times B\right)=$ $\#A\cdot$ $\#B$ ; (f) $\#\mathcal{P}(A)=2^{\#A}$ .

Solució: És clar que si $A$ i $B$ són disjunts, llavors

\#\left(A\cup B\right)=\#A+\#B

(a) Com que $\left\{A\cap B,\complement A\cap B\right\}$ és una partició de $B$ , llavors

\#B=\text{ }\#\left(A\cap B\right)+\#\left(\complement A\cap B\right)

Ara bé, com $A\subset B$ , llavors $A\cap B=A$ i, per tant, obtenim

\#B=\text{ }\#A+\#\left(\complement A\cap B\right)

En ser $\#\left(\complement A\cap B\right)\geq 0$ , deduïm

\#A\leq\text{ }\#B

(b) Com que $\left\{A,\complement A\cap B\right\}$ , $\left\{B,A\cap\complement B\right\}$ i $\left\{A\cap\complement B,\complement A\cap B,A\cap B\right\}$ constitueixen particions del conjunt $A\cup B$ , llavors

\#\left(A\cup B\right)=\#A+\#\left(B\cap\complement A\right)

\#\left(A\cup B\right)=\#A+\#\left(A\cap\complement B\right)

\#\left(A\cup B\right)=\#\left(A\cap\complement B\right)+\#\left(\complement A% \cap B\right)+\#\left(A\cap B\right)

Sumant ara les dues primeres igualtats i restant la tercera, obtenim

\#\left(A\cup B\right)=\#A+\#B-\#\left(A\cap B\right)

	$\displaystyle\#\left(A\cup B\cup C\right)$	$\displaystyle=\#\left((A\cup B)\cup C\right)$
		$\displaystyle=\#(A\cup B)+\#C-\#\left((A\cup B)\cap C\right)$
		$\displaystyle=\#A+\#B-\#\left(A\cap B\right)+\#C-\#\left((A\cup B)\cap C\right)$

Ara bé, $(A\cup B)\cap C=(A\cap C)\cup(B\cap C)$ i, per tant,

	$\displaystyle\#\left((A\cup B)\cap C\right)$	$\displaystyle=\#\left((A\cap C)\cup(B\cap C)\right)$
		$\displaystyle=\#\left(A\cap C\right)+\#\left(B\cap C\right)-\#\left((A\cap C)% \cap(B\cap C)\right)$
		$\displaystyle=\#\left(A\cap C\right)+\#\left(B\cap C\right)-\#\left(A\cap B% \cap C\right)$

Per consegüent, obtenim

	$\displaystyle\#\left(A\cup B\cup B\right)$	$\displaystyle=\#A+\#B+\#C-\#\left(A\cap B\right)$
		$\displaystyle-\#\left(A\cap C\right)-\#\left(B\cap C\right)+\#\left(A\cap B% \cap C\right)$

(d) Com que $\left\{A,\complement_{E}A\right\}$ és una partició de $E$ , llavors

\#E=\#A+\#\left(\complement_{E}A\right)

i, per tant,

\#\left(\complement_{E}A\right)=\#E-\#A

(e) Suposem que $\#A=n$ i $\#B=m$ . Sigui $\varphi:\left\{1,2,...,n\right\}\longrightarrow A$ una aplicació tal que $\varphi(i)=a_{i}\in A$ i $a_{i}\neq a_{j}$ si $i\neq j$ . Així, podem escriure

A=\left\{a_{1},a_{2},...,a_{n}\right\}

De la mateixa manera, obtenim

B=\left\{b_{1},b_{2},...,b_{m}\right\}

Llavors, els conjunts

\begin{array}[]{c}F_{1}=\left\{(a_{1},b_{1}),(a_{1},b_{2}),...(a_{1},b_{m})% \right\}\\ F_{2}=\left\{(a_{2},b_{1}),(a_{2},b_{2}),...(a_{2},b_{m})\right\}\\ \vdots\\ F_{n}=\left\{(a_{n},b_{1}),(a_{n},b_{2}),...(a_{n},b_{m})\right\}\end{array}

constitueixen una partició de $A\times B$ i, per tant,

\#\left(A\times B\right)=\#F_{1}+\#F_{2}+\cdots+\#F_{n}=n\cdot m

doncs

\#F_{1}=\#F_{2}=\cdots=\#F_{n}=m

Per tant,

\#\left(A\times B\right)=\#A\times\#B

(f) Suposem que $\#A=n$ . Sabem que $\mathcal{P}(A)$ és el conjunt els elements del qual són subconjunts d’ $A$ . Sigui $0\leq m\leq n$ , quants subconjunts de $m$ elements té $A$ ? Aquest número és per definició el número combinatori

\binom{n}{m}

que es calcula mitjançant la fórmula següent

\binom{n}{m}=\frac{n!}{m!\left(n-m\right)!}

sent el factorial d’un número $n$

n!=n\cdot(n-1)\cdot(n-2)\cdot\cdots\cdot 2\cdot 1

i, per definició, $0!=1$ . Així, tenim

\begin{array}[]{cc}\text{N\'{u}mero d'elements del subconjunt}&\text{N\'{u}% mero de subconjunts}\\ 0&\binom{n}{0}\\ 1&\binom{n}{1}\\ 2&\binom{n}{2}\\ \vdots&\vdots\\ n-1&\binom{n}{n-1}\\ n&\binom{n}{n}\end{array}

Llavors,

\#\mathcal{P}(A)=\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{n-1}+% \binom{n}{n}

Aquesta suma pot calcular-se mitjançant la fórmula de la potència del binomi de Newton

(A+B)^{n}=\binom{n}{0}A^{n}+\binom{n}{1}A^{n-1}B+\binom{n}{2}A^{n-2}B+\cdots+% \binom{n}{n-1}AB^{n-1}+\binom{n}{n}B^{n}

Prenent $A=B=1$ , resulta

(1+1)^{n}=\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{n-1}+\binom{% n}{n}

i, per consegüent, obtenim

\#\mathcal{P}(A)=2^{n}=2^{\#A}

$\square$

Exercici 2.43.

Suposem que en Joan menja cada matí ous o cereals per esmorzar durant el mes de gener. Si en 25 matins ha menjat cereals, i en 18, ous, en quants matins ha menjat ous i cereals?

Solució: Sigui $A$ el conjunt de dies del mes de gener que en Joan menja ous per esmorzar i $B$ el conjunt de dies que menja cereals. Segons la informació de l’enunciat, tenim $\#A=25$ i $\#B=18$ i, a més, és clar que $\#\left(A\cup B\right)=31$ . Llavors,

	$\displaystyle\#\left(A\cup B\right)$	$\displaystyle=\#A+\#B-\#\left(A\cap B\right)$
	$\displaystyle 31$	$\displaystyle=25+18-\#\left(A\cap B\right)$
	$\displaystyle\#\left(A\cap B\right)$	$\displaystyle=12$

Ara bé, $\#\left(A\cap B\right)$ representa els dies que en Joan menja ous i cereals per esmorzar durant el mes de gener. Per tant, en Joan menja ous i cereals en 12 matins. $\square$

Exercici 2.44.

Se sap que dels 30 alumnes d’una classe 15 juguen al ping-pong i 20 al tennis. A més, no hi ha cap alumne que no practiqui algun d’aquests dos esports. Quants alumnes practiquen els dos esports alhora?

Solució: Sigui $A$ el conjunt d’alumnes de la classe que practiquen ping-pong i $B$ el conjunt d’alumnes que practiquen tennis. Segons l’enunciat, $\#A=15$ i $\#B=20$ . Com sabem també que no hi ha cap alumne que no practiqui algun d’aquests dos esports, tenim que $\#\left(A\cup B\right)=30$ . Llavors,

	$\displaystyle\#\left(A\cup B\right)$	$\displaystyle=\#A+\#B-\#\left(A\cap B\right)$
	$\displaystyle 30$	$\displaystyle=15+20-\#\left(A\cap B\right)$
	$\displaystyle\#\left(A\cap B\right)$	$\displaystyle=5$

i, per tant, hi ha 5 alumnes de la classe que practiquen tots dos esports. $\square$

Exercici 2.45.

En una classe, 30 alumnes llegeixen el diari $A$ , 20 llegeixen el $B$ , 13 llegeixen l’i $A$ el $C$ , 10 llegeixen el $B$ però no el $C$ , 24 no llegeixen $C$ , 7 llegeixen l’i $A$ el $C$ però no el $B$ , 9 llegeixen el $C$ però no el $A$ ni el $B$ , i 11 llegeixen el $A$ però no el $B$ ni el $C$ . (a) Quants alumnes llegeixen almenys un dels tres diaris? (b) Quants alumnes hi ha en la classe?

Solució: Reunint la informació en un diagrama de Venn, obtenim

A partir d’aquest diagrama podem respondre directament les qüestions plantejades. Tot i això, aquí el farem mitjançant les fórmules estudiades sobre cardinals de conjunts finits.

Sigui $E$ el conjunt d’alumnes de la classe, $A$ el conjunt d’alumnes d’aquesta classe que llegeixen el diari $A$ , $B$ el conjunt d’alumnes que llegeixen el diari $B$ , i $C$ el conjunt d’alumnes que llegeixen el diari $C$ .

Per l’enunciat, sabem que $\#A=30$ , $\#B=20$ , $\#\left(A\cap C\right)=13$ , $\#\left(B\cap\complement C\right)=10$ , $\#\complement C=24$ , $\#\left(A\cap C\cap\complement B\right)=7$ , $\#\left(C\cap\complement A\cap\complement B\right)=9$ i $\#\left(A\cap\complement B\cap\complement C\right)=11$ .

(a) Ens demanen calcular $\#\left(A\cup B\cup C\right)$ . Segons la informació que tenim, els conjunts $A\cap C\cap\complement B$ , $C\cap\complement A\cap\complement B$ , $A\cap\complement B\cap\complement C$ i $B$ són disjunts i, a més, com

A\cup B\cup C=\left(A\cap C\cap\complement B\right)\cup\left(C\cap\complement A% \cap\complement B\right)\cup\left(A\cap\complement B\cap\complement C\right)\cup B

s’obté

	$\displaystyle\#\left(A\cup B\cup B\right)$	$\displaystyle=\#\left(A\cap C\cap\complement B\right)+\#\left(C\cap\complement A% \cap\complement B\right)+\#\left(A\cap\complement B\cap\complement C\right)+\#B$
		$\displaystyle=7+9+11+20$
		$\displaystyle=47$

Per tant, hi ha 47 alumnes que llegeixen almenys un dels tres diaris.

(b) Ens demanen en aquest cas $\#E$ . Els conjunts $A\cap B\cap C$ , $A\cap\complement B\cap C$ són disjunts i, a més,

A\cap C=\left(A\cap B\cap C\right)\cup\left(A\cap\complement B\cap C\right)

Per tant,

	$\displaystyle\#\left(A\cap C\right)$	$\displaystyle=\#\left(A\cap B\cap C\right)+\#\left(A\cap\complement B\cap C\right)$
	$\displaystyle 13$	$\displaystyle=\#\left(A\cap B\cap C\right)+7$

Llavors, $\#\left(A\cap B\cap C\right)=6$ . D’altra banda, els conjunts $B\cap\complement C$ , $A\cap B\cap C$ i $\complement A\cap B\cap C$ són disjunts i, a més,

B=\left(B\cap\complement C\right)\cup\left(A\cap B\cap C\right)\cup\left(% \complement A\cap B\cap C\right)

Aleshores,

	$\displaystyle\#B$	$\displaystyle=\#\left(B\cap\complement C\right)+\#\left(A\cap B\cap C\right)+% \#\left(\complement A\cap B\cap C\right)$
	$\displaystyle 20$	$\displaystyle=10+6+\#\left(\complement A\cap B\cap C\right)$

Per tant, $\#\left(\complement A\cap B\cap C\right)=4$ . Finalment, els conjunts $A\cap C$ , $\complement A\cap B\cap C$ i $A\cap\complement B\cap\complement C$ són disjunts i, a més,

C=\left(A\cap C\right)\cup\left(\complement A\cap B\cap C\right)\cup\left(A% \cap\complement B\cap\complement C\right)

Per tant,

	$\displaystyle\#C$	$\displaystyle=\#\left(A\cap C\right)+\#\left(\complement A\cap B\cap C\right)+% \#\left(A\cap\complement B\cap\complement C\right)$
		$\displaystyle=13+4+9$
		$\displaystyle=26$

i, com

\#\complement C=\#E-\#C

deduïm que

	$\displaystyle\#E$	$\displaystyle=\#\complement C+\#C$
		$\displaystyle=24+26$
		$\displaystyle=50$

és a dir, hi ha 50 alumnes en classe. $\square$

Exercici 2.46.

En una acarnissada batalla almenys el 70 % dels combatents perden un ull, almenys un 75 % perden una orella, com a mínim un 80 % perden un braç i almenys el 85 % una cama. Quants combatents han perdut almenys les quatre coses?

Solució: Sigui $A$ el conjunt de combatents que perden un ull, $B$ el conjunt dels quals perden una orella, $C$ el conjunt dels quals perden un braç i $D$ el conjunt dels quals perden una cama. Per a simplificar els càlculs suposarem que hi ha 100 combatents en la batalla (En treballar amb tants per cent és igual el nombre inicial de combatents). Llavors, per l’enunciat, tenim que $\#A\geq 70$ , $\#B\geq 75$ , $\#C\geq 80$ i $\#D\geq 85$ . Volem calcular el valor mínim de $\#\left(A\cap B\cap C\cap D\right)$ .

Sabem que

\#\left(\left(A\cap B\right)\cup\left(C\cap D\right)\right)=\#\left(A\cap B% \right)+\#\left(C\cap D\right)-\#\left(A\cap B\cap C\cap D\right)

Aleshores es té també

\#\left(A\cap B\cap C\cap D\right)=\#\left(A\cap B\right)+\#\left(C\cap D% \right)-\#\left(\left(A\cap B\right)\cup\left(C\cap D\right)\right)

Ara bé, d’altra banda, sabem que

	$\displaystyle\#\left(A\cap B\right)$	$\displaystyle=\#A+\#B-\#\left(A\cup B\right)$
		$\displaystyle\geq 70+75-100$
		$\displaystyle=45$

	$\displaystyle\#\left(C\cap D\right)$	$\displaystyle=\#C+\#D-\#\left(C\cup D\right)$
		$\displaystyle\geq 80+85-100$
		$\displaystyle=65$

Llavors, d’aquests dos resultats deduïm que

\#\left(A\cap B\cap C\cap D\right)\geq 45+65-100=10

i com que $0\leq$ $\#\left(\left(A\cap B\right)\cup\left(C\cap C\right)\right)\leq 100$ , s’obté que almenys el 10 % perd les quatre coses. $\square$

Exercici 2.47.

En una reunió hi ha més homes que dones, més dones que beuen que homes que fumen i més dones que fumen i no beuen que homes que no beuen ni fumen. Demostrar que hi ha menys dones que no beuen ni fumen que homes que beuen i no fumen.

Solució: Fem el següent diagrama per a descriure la informació de l’enunciat.

Si $H$ és el conjunt d’homes i $M$ el de dones, llavors per l’enunciat es compleix que

\#H>\#M

Si $F$ és el conjunt de persones fumadores i $B$ és el conjunt de persones que beuen, llavors per l’enunciat també es compleix

\#\left(M\cap B\right)>\#\left(H\cap F\right)

\#\left(M\cap F\cap\complement B\right)>\#\left(H\cap\complement B\cap% \complement F\right)

Cal provar que

\#\left(M\cap\complement B\cap\complement F\right)<\#\left(H\cap B\cap% \complement F\right)

Amb l’ajuda del diagrama anterior, podem escriure

\#H=a+c+e+g>b+d+f+h=\#M

\#\left(M\cap B\right)=d+f>a+c=\#\left(H\cap F\right)

\#\left(M\cap F\right)=b>g=\#\left(H\cap\complement B\cap\complement F\right)

Sumant membre a membre les tres desigualtats anteriors, obtenim

\begin{array}[]{ccc}a+c+e+g+d+f+b>b+d+f+h+a+c+g&\Longrightarrow&e>h\end{array}

és a dir,

\#\left(M\cap\complement B\cap\complement F\right)=b<e=\#\left(H\cap B\cap% \complement F\right)

$\square$