PUERTA | GATE-CS-2016 (Conjunto 2) | Pregunta 38

Considere un conjunto U de 23 compuestos diferentes en un laboratorio de química. Hay un subconjunto S de U de 9 compuestos, cada uno de los cuales reacciona exactamente con 3 compuestos de U. Considere las siguientes afirmaciones:

I.  Each compound in U \ S reacts with an odd number of compounds.
II.  At least one compound in U \ S reacts with an odd number of compounds.
III.  Each compound in U \ S reacts with an even number of compounds. 

¿Cuál de las afirmaciones anteriores SIEMPRE ES CIERTA?

(A) Solo I
(B) Solo II
(C) Solo III
(D) Ninguna

Respuesta: (B)
Explicación: La respuesta es B. Esta es una pregunta de teoría de grafos.

“\” es la operación de diferencia de conjuntos. Igual que U – S.

Dado que U es un conjunto universal, U\S daría el complemento de S = S’
Sea S que contenga los compuestos numerados {1,2,3…8, 9} por lo que U\S contiene los compuestos {10, 11, 12…. 22, 23}

Considere estos compuestos como vértices de un gráfico.
Una arista entre dos vértices indica que los compuestos reaccionan entre sí.

Este gráfico NO tiene una causa de múltiples aristas que no tenga sentido.
No hay bordes dirigidos porque si un compuesto reacciona con otro, también significa que el otro también reacciona con él. Un solo borde representa la reacción entre ambos.
NO tiene bucles porque el compuesto no reacciona consigo mismo.

Por lo tanto, el gráfico es un gráfico simple no dirigido.

Sabemos que “Un grafo no dirigido tiene un número par de vértices de grado impar”

9 vértices de este gráfico tienen grado 3 (grado impar) porque 9 compuestos reaccionan con otros 3 compuestos.
Por lo tanto, debe haber al MENOS 1 vértice más que debe tener un grado impar.
Este compuesto adicional debe pertenecer a U\S porque ya se han contabilizado 9 compuestos en S.
Esto implica que la declaración II en la pregunta es VERDADERA.

Otras 2 declaraciones son falsas.
Declaración III: considere que los 9 compuestos en S reaccionan con los mismos 3 compuestos en U\S, por ejemplo, con {20, 21, 22}, por lo tanto, todos los compuestos en U\S reaccionan con cero o 9 compuestos pero no con un número par.
De manera similar, se puede demostrar que la afirmación I es incorrecta al visualizar el gráfico.

Cuestionario de esta pregunta