No veo qué quieren decir con la biyección de tríos de subconjuntos de $\{1, \ldots, 10\}$ y la matriz de $10\times3$ con entradas $0, 1$?
¿Cómo se crea eso?
¿Qué han hecho alguna vez las matrices para ofenderte?
Respuestas
¿Demasiados anuncios?
John Fouhy
Puntos
759
Para cualquier elemento $x \in \{1,\ldots,10\}$, para satisfacer las restricciones, $x$ debe pertenecer exactamente a 1 o exactamente a 2 de los conjuntos $A_1,A_2,A_3$. Esto te da 6 posibilidades por elemento (¿por qué?), para un total de $6^{10}$ posibilidades.
No te preocupes por la matriz; esto es solo una forma elegante de expresar el mismo argumento.
(+1) Gran respuesta @Yuval. ¿Pero por qué solo $1$ o $2$ de los conjuntos $A_1, A_2, A_3$ aunque?
@Amad27 si un elemento $x$ perteneciera a todos los conjuntos, entonces tendríamos $x \in A_1 \cap A_2 \cap A_3 \neq \emptyset$
Por ejemplo, supongamos que los tres conjuntos son \begin{align} A_1 & = \{1,5,6,8\} \\ A_2 & = \{1,2,3,4,10\} \\ A_3 & = \{2,4,5,7,9,10\} \end{align} (Nótese que $A_1\cup A_2\cup A_3=\{1,2,3,4,5,6,7,8,9,10\}$ y $A_1\cap A_2\cap A_3=\varnothing$.)
Entonces la matriz de $10\times3$ es $$ \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix} $$ La primera columna de la matriz corresponde al conjunto $A_1$. Tiene un $1$ en las filas $1$, $5$, $6$ y $8$ porque los miembros de $A_1$ son $1,5,6,8$. De manera similar, la segunda y tercera columnas corresponden respectivamente a $A_2$ y $A_3$.
Michael Hardy (+1), al final sin embargo. Cuando dicen: "El número de posibilidades de cada fila de tal matriz es $2^3 - 2 = 6$" ¿a qué posibilidad se refieren? Además, ¿cómo es $2^3 - 2$ de todos modos?
Hay ocho $=2^3$ posibles filas si no se requiere que la unión de los tres conjuntos contenga los diez números y también no se requiere que la intersección esté vacía. Esas ocho son: $(0,0,0),\ (0,0,1),\ (0,1,0),\ (1,0,0),\ (0,1,1),\ (1,0,1),\ (1,1,0),\ (1,1,1)$. El requisito de no intersección excluye $(1,1,1)$, y el requisito de que todos los diez números estén incluidos excluye $(0,0,0)$. ${}\qquad{}$
Ahora entendí =) Pero no entiendo algo. ¿Cómo el número de posibilidades de las filas de las matrices da la respuesta final?
0 votos
No necesitas escribir $10x3$; puedes escribir $10\times3$. Hice la edición correspondiente. ${}\qquad{}$
0 votos
@chi: El mapa es una biyección entre el conjunto de todos los tríos ordenados de subconjuntos (sin las condiciones i y ii), y el conjunto de todos las matrices binarias de tamaño 10x3.
0 votos
@HenningMakholm Tienes razón. Malinterpreté la primera parte.