16.3: Sistemas de Representantes Distintos
- Page ID
- 114335
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Supongamos que comenzamos a rellenar un cuadrado latino, una fila a la vez, en cada paso asegurando que ningún elemento haya aparecido aún más de una vez en una columna (o en una fila). ¿Bajo qué condiciones será imposible completar esto a una plaza latina? Aunque puede que no sea inmediatamente obvio, la respuesta a esta pregunta la puede encontrar en un conocido teorema publicado por Philip Hall en\(1935\), sobre sistemas de distintos representantes.
Definición: Word
\(T_1 . . . , T_n\)Dejen ser conjuntos. Si existe\(a_1, . . . , a_n\) todo distinto tal que para cada\(1 ≤ i ≤ n\),\(a_i ∈ T_i\), entonces\(\{a_1, . . . a_n\}\) formar un sistema de representantes distintos (DEG) para\(T_1, . . . , T_n\).
Ejemplo\(\PageIndex{1}\)
La universidad está golpeando a un comité estudiantil sobre el tema de las tutorías. Para cada una de\(5\) las Facultades, piden a los alumnos que elijan a un representante que esté tomando clases de esa facultad. No quieren que un estudiante intente representar a más de una facultad. Los candidatos son:
- Joseph, quien está cursando cursos de Artes y Ciencias, Bellas Artes, Administración y Educación;
- René, quien está cursando cursos de Ciencias de la Salud;
- Claire, quien está cursando cursos de Educación y Ciencias de la Salud;
- Sandra, quien está cursando cursos de Administración, Bellas Artes y Ciencias de la Salud;
- Laci, quien está cursando cursos de Educación y Ciencias de la Salud; y
- Jing, quien está tomando cursos de Educación.
¿Se puede llenar el comité?
Solución
La respuesta es no. Para las tres Facultades de Artes y Ciencias, Bellas Artes y Administración, sólo hay dos posibles representantes estudiantiles: Joseph (que podría representar a cualquiera de las tres) y Sandra (que podría representar bien a Bellas Artes o Administración). Por lo que no es posible elegir a un alumno para representar a cada una de las cinco Facultades, sin permitir que uno de estos alumnos ocupe dos roles.
En el Ejemplo 16.3.1, observamos que podríamos encontrar una colección de los conjuntos a representar, que colectivamente tuvo menos representantes posibles que los conjuntos que hay en la colección. Es fácil ver que si esto sucede, no puede haber un sistema de representantes distintos para los conjuntos.
Lo que Philip Hall probó es lo contrario: a menos que tengamos una obstrucción de este tipo, siempre es posible multar a un sistema de representantes distintos.
Teorema\(\PageIndex{1}\): Hall's Theorem
El acervo de conjuntos\(T_1, . . . , T_n\) tiene un sistema de representantes distintos si y sólo si por cada uno\(1 ≤ k ≤ n\), la unión de alguno\(k\) de los conjuntos tiene al menos cardinalidad\(k\).
A este teorema se le suele denominar “Teorema del matrimonio de Hall”, ya que uno de los problemas que resuelve se puede afirmar de la siguiente manera. Supongamos que tenemos una colección de hombres y una colección de mujeres. Cada una de las mujeres tiene una lista de hombres que le gustan (de la colección). ¿Cuándo es posible casar a cada una de las mujeres con un hombre que le gusta? (El contexto es histórico, y la suposición de la época era que toda mujer querría casarse con un hombre.)
Hemos visto que una de las dos implicaciones del Teorema de Hall es fácil de probar. Aquí no intentaremos probar la otra implicación, sino que nos enfocaremos en usar el resultado. Aquí hay algunos ejemplos y ejercicios. Para completar, proporcionamos una prueba del Teorema de Hall al final de este capítulo.
Ejemplo\(\PageIndex{2}\)
Vamos\(A_1 = \{a, b, c, d\}\),\(A_2 = \{b, c\}\),\(A_3 = \{b\}\),\(A_4 = \{b, c\}\). ¿Esta colección de conjuntos tiene un sistema de representantes distintos? Si es así, encuentra uno; si no, explica por qué.
Solución
La respuesta es que esta colección de conjuntos no tiene sistema de representantes distintos, porque la unión de tres conjuntos\(A_2\),\(A_3\), y sólo\(A_4\) tiene dos elementos:\(b\) y\(c\).
Ejemplo\(\PageIndex{3}\)
Vamos\(A_1 = \{a, d\}\),\(A_2 = \{a, c\}\),\(A_3 = \{b, c\}\),\(A_4 = \{c, d\}\). ¿Esta colección de conjuntos tiene un sistema de representantes distintos? Si es así, encuentra uno; si no, explica por qué.
Solución
Esta colección de conjuntos sí cuenta con un sistema de representantes distintos: tomar\(a\) para\(A_1\)\(A_2\),\(c\) para\(A_3\),\(b\) para y\(d\) para\(A_4\). Para mayor claridad, subrayamos a los representantes en la siguiente lista de los conjuntos:\(A_1 = \{\underline{a}, d\}\),\(A_2 = \{a, \underline{c}\}\),\(A_3 = \{\underline{b}, c\}\),\(A_4 = \{c, \underline{d}\}\).
(De hecho, también tiene otro sistema de representantes distintos: tomar\(d\) por\(A_1\),\(a\) para\(A_2\)\(A_3\),\(b\) para y\(c\) para\(A_4\):\(A_1 = \{a, \underline{d}\}\),,\(A_2 = \{\underline{a}, c\}\),\(A_3 = \{\underline{b}, c\}\),\(A_4 = \{\underline{c}, d\}\).)
Ejercicio\(\PageIndex{1}\)
Para cada colección de conjuntos, determinar si tiene o no un sistema de representantes distintos. Si es así, encuentra uno; si no, explica por qué.
1)\(A_1 = \{x\}\),\(A_2 = \{y, z\}\),\(A_3 = \{x, y\}\).
2)\(A_1 = \{u, v, w, x, y, z\}\),\(A_2 = \{v, w, y\}\),\(A_3 = \{w, x, y\}\),\(A_4 = \{v, w, x, y\}\),\(A_5 = \{v, x, y\}\),\(A_6 = \{v, y\}\).
3)\(A_1 = \{x\}\),\(A_2 = \{y\}\),\(A_3 = ∅\).
4)\(A_1 = \{x, z\}\),\(A_2 = \{y\}\),\(A_3 = \{x, y, z\}\).
5)\(T_1 = \{a, b, c, d\}\),\(T_2 = \{a, b, c\}\),\(T_3 = \{a\}\),\(T_4 = \{c\}\).
6)\(U_1 = \{x, y\}\),\(U_2 = \{y, z\}\),\(U_3 = ∅\).
7)\(V_1 = \{e, f\}\),\(V_2 = \{e, g\}\),\(V_3 = \{e, h\}\),\(V_4 = \{f, g\}\),\(V_5 = \{h, i\}\).
8)\(W_1 = \{+, −, ×, ÷, 0\}\),\(W_2 = \{+, −, ×\}\),\(W_3 = \{+, ×\}\),\(W_4 = \{×, −\}\),\(W_5 = \{+, −\}\).
Volvamos a nuestra pregunta original sobre los cuadrados latinos. Para responder a esto, primero damos una importante consecuencia general del Teorema de Hall.
Proposición\(\PageIndex{1}\)
Supongamos que\(T_1, . . . , T_n\) es una colección de conjuntos cada uno de los cuales contiene exactamente\(r\) elementos. Además, supongamos que ningún elemento aparece en más\(r\) de los conjuntos. Entonces esta colección tiene un sistema de representantes distintos.
- Prueba
-
Por el Teorema de Hall, debemos demostrar que para cada uno\(1 ≤ k ≤ n\), la unión de cualquiera\(k\) de los conjuntos\(T_1, . . . , T_n\) tiene al menos cardinalidad\(k\). \(k ∈ {1, . . . , n}\)Sea arbitrario, y elija arbitrariamente\(k\) de los conjuntos\(T_{j_1}, . . ., T_{j_k}\). Si\(k ≤ r\) entonces ya que cada uno\(T_{j_i}\) tiene\(r\) elementos, su unión debe tener al menos\(r ≥ k\) elementos, según se desee.
Supongamos por otro lado eso\(k > r\). Entre los\(k\) conjuntos de\(r\) elementos, aparece un total de\(kr\) elementos (contando cada elemento cada vez que aparece). Dado que cada elemento aparece en la mayoría\(r\) de los conjuntos, debe darse el caso de que al menos aparezcan elementos\(k\) distintos. Esto completa la prueba.
Ya podemos responder a la pregunta sobre los cuadrados latinos.
Teorema\(\PageIndex{2}\)
Supongamos que se\(n\) han llenado\(m\) filas de un cuadrado latino de orden, donde\(m < n\), y que a este punto ninguna entrada aparece más de una vez en ninguna fila o columna. Entonces se puede agregar otra fila al cuadrado latino, manteniendo la condición de que ninguna entrada aparezca más de una vez en ninguna fila o columna.
- Prueba
-
For\(1 ≤ i ≤ n\), deja\(T_i\) ser el conjunto de elementos que aún no han aparecido en columna\(i\) (a partir de las entradas en las primeras\(m\) filas). Así que\(T_i\) puede pensarse como el conjunto de entradas permitidas para la\(i^{\text{th}}\) columna de la nueva fila. Observe que cada uno\(T_i\) tiene cardinalidad\(n − m\) (el número de filas que aún están vacías). La tarea de encontrar una nueva fila cuyas entradas sean distintas, y cuya\(i^{\text{th}}\) entrada provenga del conjunto\(T_i\) de entradas permitidas para esa columna, equivale a encontrar un sistema de representantes distintos para los conjuntos\(T_1, . . . , T_n\). Así, debemos demostrar que la colección\(T_1, . . . , T_n\) cuenta con un sistema de representantes distintos.
Observe también que cada elemento ha aparecido una vez en cada una de las primeras\(m\) filas, y así ha aparecido precisamente en\(m\) de las columnas. Por lo tanto, hay exactamente\(n − m\) de las columnas en las que aún no ha aparecido. En otras palabras, cada elemento aparece exactamente en\(n − m\) los conjuntos.
Ahora podemos aplicar la Proposición 16.3.1, con\(r = n − m\) para ver que nuestros conjuntos sí cuentan con un sistema de representantes distintos. Esto se puede utilizar para formar una nueva fila para el cuadrado latino.
Corolario\(\PageIndex{1}\)
Supongamos que se\(n\) han llenado\(m\) filas de un cuadrado latino de orden, donde\(m < n\), y que a este punto ninguna entrada aparece más de una vez en ninguna fila o columna. Esta estructura siempre se puede completar a un cuadrado latino.
- Prueba
-
Siempre y cuando\(m < n\), podemos aplicar repetidamente el Teorema 16.3.2 para deducir que es posible agregar una fila. Una vez que realmente encuentre una fila que se pueda agregar (tenga en cuenta que la declaración del Teorema de Hall no explica cómo hacerlo), háganlo. Eventualmente, este proceso resultará en un cuadrado completo.
El Teorema de Hall también se puede utilizar para probar un caso especial de un resultado que probamos anteriormente, el Teorema 14.1.3. El caso especial que podemos probar con el Teorema de Hall, es el caso donde cada vértice tiene la misma valencia.
Teorema\(\PageIndex{3}\)
Si\(G\) es una gráfica bipartita en la que cada vértice tiene la misma valencia, entonces cualquier bipartición establece\(V_1\) y\(V_2\) tiene la misma cardinalidad, y hay un conjunto de\(|V_1|\) bordes que pueden colorearse correctamente con el mismo color.
- Prueba
-
Dejar\(k\) ser la valencia de cada vértice, y para algunos conjuntos arbitrarios de bipartición\(V_1\) y\(V_2\), let\(n = |V_1|\). Por una ligera adaptación del lema de apretón de manos de Euler, tomando en cuenta el hecho de que cada borde tiene exactamente uno de sus extremos en\(V_1\), vemos eso\(nk = |E|\). Por el mismo argumento,\(k|V_2| = |E|\), que obliga\(|V_2| = n = |V_1|\). Dado que la bipartición era arbitraria, sigue la primera declaración.
Vamos\(V_1 = \{v_1, . . . , v_n\}\). Por cada\(1 ≤ i ≤ n\), vamos
\[T_i = \{u ∈ V | u ∼ v_i\}.\]
Un sistema de distintos representantes para los conjuntos\(T_1, . . . , T_n\) producirá\(n = |V_1|\) bordes que pueden ser coloreados correctamente con el mismo color.
Observe que cada conjunto\(T_i\) tiene cardinalidad\(k\) (ya que esta es la valencia de cada vértice), y cada vértice aparece exactamente en\(k\) los conjuntos (nuevamente porque esta es la valencia del vértice). Por lo tanto, por la Proposición 16.3.1, existe un sistema de representantes distintos para\(T_1, . . . , T_n\). De ahí que podamos encontrar\(n = |V_1|\) bordes que pueden ser correctamente coloreados con el mismo color.
Corolario\(\PageIndex{2}\)
Si\(G\) es una gráfica bipartita en la que cada vértice tiene la misma valencia\(k\), entonces sus bordes pueden ser coloreados correctamente usando\(k\) colores.
- Prueba
-
Repita los siguientes\(k\) tiempos de paso: encuentre un conjunto de bordes que puedan ser coloreados correctamente. Colorearlos con un nuevo color y eliminarlos de la gráfica.
En cada etapa, el Teorema 16.3.3 nos dice siempre que cada vértice tenga la misma valencia, podemos encontrar un conjunto de bordes que están correctamente coloreados, uno de los cuales es incidente con cada vértice de la gráfica. Dado que la valencia de cada vértice se reduce exactamente en uno cuando eliminamos dicho conjunto de aristas, en cada etapa cada vértice tendrá la misma valencia.
Para concluir el capítulo, proporcionamos una prueba del Teorema de Hall. Como se señaló anteriormente, una dirección es obvia, por lo que demostramos sólo la otra dirección.
Teorema\(\PageIndex{4}\): Hall's Theorem
El acervo de conjuntos\(T_1, . . . , T_n\) tiene un sistema de representantes distintos si por cada uno\(1 ≤ k ≤ n\), la unión de alguno\(k\) de los conjuntos tiene al menos cardinalidad\(k\).
- Prueba
-
Esto lo demostraremos por una fuerte inducción en el número de sets,\(n\).
Caso base:\(n = 1\). Si un solo conjunto tiene un elemento, entonces ese conjunto tiene un representante. Esto completa la prueba del caso base.
Paso inductivo: Comenzamos con la hipótesis inductiva. Que\(m ≥ 1\) sea arbitrario. Supongamos que siempre que\(1 ≤ i ≤ m\), y una colección de\(i\) conjuntos\(T_1, . . . , T_i\) tenga la propiedad de que para cada\(1 ≤ k ≤ i\), la unión\(k\) de cualquiera de los conjuntos tenga al menos cardinalidad\(k\), entonces esa colección de conjuntos tiene un sistema de representantes distintos.
Queremos deducir que siempre que tengamos una colección de\(m + 1\) conjuntos con la propiedad que para cada\(1 ≤ k ≤ m + 1\), la unión de cualquiera\(k\) de los conjuntos tiene al menos cardinalidad\(k\), entonces esa colección de conjuntos tiene un sistema de representantes distintos. Let\(T_1, . . . , T_{m+1}\) Ser tal colección de conjuntos.
Observamos la subcolección de conjuntos\(T_1, . . . , T_m\), y consideramos dos casos. Primero, supongamos que para cada\(1 ≤ k ≤ m\), la unión de cualquiera\(k\) de estos conjuntos tiene al menos cardinalidad\(k + 1\). En este caso, tomar cualquier elemento\(t ∈ T_{m+1}\) (que por hipótesis no está vacío) para ser el representante de\(T_{m+1}\), y eliminar este elemento de cada uno de los otros conjuntos. Por el caso estamos en, para cada\(1 ≤ k ≤ m\), la unión de cualquiera\(k\) de los conjuntos\(T_1 − \{t\}, . . . , T_m − \{t\}\) todavía tiene cardinalidad al menos\(k\), (hemos eliminado sólo el elemento\(t\) de esta unión, que anteriormente tenía cardinalidad al menos\(k + 1\)). Así podemos aplicar nuestra hipótesis de inducción para encontrar un sistema de representantes distintos para\(T_1, . . . , T_m\) que no incluya el elemento\(t\). Esto completa un sistema de representantes distintos para nuestra colección completa de conjuntos.
El otro caso es que hay alguna\(1 ≤ k ≤ m\) y cierta colección\(k\) de los conjuntos\(T_1, . . . , T_m\), cuya unión tiene cardinalidad precisamente\(k\). Por nuestra hipótesis de inducción, existe un sistema de representantes distintos para estos\(k\) conjuntos. De los otros\(m + 1 − k\) conjuntos (observe eso\(1 ≤ m + 1 − k ≤ m\)), eliminar los\(k\) elementos que estaban en la unión de los\(k\) conjuntos originales. Considera cualquiera\(k'\) de estos conjuntos ajustados, con\(1 ≤ k' ≤ m + 1 − k\). Observe que la unión de los\(k + k'\) conjuntos constituidos por los\(k\) conjuntos originales junto con estos\(k'\) conjuntos debe haber contenido al menos elementos\(k + k'\) distintos por hipótesis, por lo que después de eliminar los\(k\) representantes de los\(k\) conjuntos originales (que son los únicos elementos en esos conjuntos), estos\(k'\) conjuntos deben tener al menos elementos\(k'\) distintos en su unión. Por lo tanto, podemos aplicar nuestra hipótesis de inducción a estos otros conjuntos\(m + 1 − k\) ajustados, y ver que ellos también tienen un sistema de representantes distintos, ninguno de los cuales se encuentra entre los\(k\) representantes de los\(k\) conjuntos originales. La combinación de estos dos sistemas de representantes distintos produce un sistema de representantes distintos para la colección completa de conjuntos.
Ejercicio\(\PageIndex{2}\)
1) Onyx está haciendo algunas investigaciones sobre lo que la gente aprende al visitar diferentes países. Ella tiene un conjunto de preguntas que deben ser respondidas por alguien que haya visitado el país. Antes de lanzar completamente el estudio, quiere probar las preguntas a algunos de sus amigos. Dado que las preguntas son las mismas para diferentes países, no quiere que una persona responda las preguntas para más de un país, ya que eso podría sesgar los resultados. De sus amigos cercanos, las siguientes personas han visitado los siguientes países:
- Inglaterra: Adam, Ella, Justin
- Gales: Adán, Justin, Fe, Cayla
- Escocia: Bryant, Justin, Ella
- Irlanda: Adam, Bryant, Justin
- Alemania: Cayla, Bryant, Justin, Faith, Denise
- Francia: Ella, Justin, Bryant
- Italia: Adam, Ella, Bryant
Demostrar que Onyx no puede encontrar siete amigos diferentes, cada uno de los cuales ha visitado uno diferente de estos países.
2) ¿Se puede completar lo siguiente a una plaza\(4 \times 4\) latina? ¿A esto se aplica el teorema de Hall? Si no, ¿por qué no?
\( 1\; \; 2\; \; 3\; \; 4 \\ 4\; \; 1\; \; 2\; \; 3 \\ 2\; \; 4\; \;\;\;\;\;\;\;\\ \)
3) Mostrar (por ejemplo) que es posible tener una gráfica bipartita en la que los conjuntos bipartitos tengan la misma cardinalidad\(k\) y la valencia de cada vértice sea\(3\) o bien\(4\), pero ningún conjunto de\(k\) aristas puede colorearse correctamente con un solo color.
4) ¿Cómo sabe (sin encontrar realmente una terminación) que lo siguiente se puede completar a un cuadrado latino de orden\(7\)?
\( 1\; \; 2\; \; 3\; \; 4\;\;5\;\;6\;\;7 \\ 2\; \; 4\; \; 7\; \; 6\;\;1\;\;5\;\;3 \\ 3\; \; 7\; \; 4\; \; 2\;\;6\;\;1\;\;5 \\ 4\; \; 6\; \; 2\; \; 5\;\;3\;\;7\;\;1 \\ \)
5) Encontrar una terminación del cuadrado latino parcial en Problema\(4\).
6) Para cada una de estas gráficas bipartitas\(V_1 = \{a, b, c, d, e, f\}\), vamos, y determinar si existe un conjunto de aristas\(|V_1|\) disjuntas. (En otras palabras, determine si hay un conjunto de\(|V_1|\) bordes que puedan colorearse correctamente con el mismo color).
(a)
b)
c)