Problema de lógica de combinaciones
Tres testigos de un crimen no quisieron denunciar directamente al criminal a un detective. El delincuente es uno de los seis sospechosos (no los testigos) encontrados en la escena del crimen. Luego, un detective propuso un juego a los testigos:
Todas las combinaciones de 4 nombres elegidos entre los 6 sospechosos están escritas en tarjetas diferentes.
El primer testigo W1 selecciona una tarjeta que contiene el nombre del criminal, luego el testigo W2 selecciona otra tarjeta que también contiene el nombre del criminal, luego W3 hace lo mismo, luego W1 elige de nuevo, y así sucesivamente hasta que el detective puede descubrir el criminal por eliminación.
¿Cuál es la menor cantidad y la mayor cantidad de selecciones de tarjetas que podrían ser necesarias para que se revele al criminal?
Respuestas
La menor cantidad de tarjetas que se pueden necesitar es:
Tres. No se puede hacer con dos o menos cartas, porque cualquier par de cartas contiene al menos dos nombres en común, por lo que dos cartas solo pueden reducir el número de posibilidades a 2.
La mayor cantidad de tarjetas que se pueden necesitar es:
Siete. Un conjunto de cartas elegido no determina al criminal solo si hay al menos dos nombres comunes a todas las cartas seleccionadas. Para cualquier par de nombres, hay$6 = {4 \choose 2}$tarjetas que contienen ambos nombres, por lo que es posible que un conjunto de seis tarjetas no determine al criminal. La séptima carta debe poseer uno de estos nombres y no el otro, determinando de forma única al criminal.
Primero nota que
existen $\binom{6}{4}$cartas en total, y cada selección de cartas revela los nombres de dos personas inocentes entre los sospechosos.
Si hay reemplazo de tarjetas, entonces el mayor número posible sería infinito, ya que todos los testigos podrían seguir eligiendo la misma tarjeta una y otra vez. Asumamos que no hay reemplazo; entonces
cada selección de cartas revela un par diferente de personas inocentes.
Número mínimo
Tres
porque
en el mejor de los casos, las parejas inocentes reveladas deben estar lo más disociadas posible. Primero W1 elimina a dos sospechosos, luego W2 elimina a otros dos sospechosos, luego W3 elimina a uno de los dos últimos reminantes (más uno que ya ha sido eliminado). Entonces se conoce la respuesta.
Mayor numero
Siete
porque
en el peor de los casos, los testigos continúan sin dar información adicional durante el mayor tiempo posible.
Después de la primera selección de W1, conocemos a dos personas inocentes. Luego, después de W2, debemos conocer al menos a tres personas inocentes. Entonces es posible que la selección de W3 no nos brinde información adicional: por ejemplo, las parejas inocentes seleccionadas son$AB$ entonces $AC$ entonces $BC$. Pero entre esas tres personas inocentes solo hay tres formas de seleccionar dos, por lo que con la selección de la cuarta carta (nuevamente por W1) debemos tener un cuarto nombre inocente.
En el peor de los casos, todos los testigos podrían seguir dándonos nombres inocentes de esos mismos cuatro durante el mayor tiempo posible. Pero solo hay$\binom{4}{2}=6$posibles parejas para elegir entre cuatro nombres, por lo que la selección de la séptima carta debe darnos un quinto nombre inocente. Lo cual es suficiente para identificar al criminal.