Publicamos la solución al divertimento de las alineaciones de baloncesto. Gracias a Marcos Jiménez y Manuel Zambrana por la solución que nos han enviado.
Divertimento:
Los responsables de un equipo de baloncesto quieren organizar una curiosa campaña con sus socios para celebrar que han llegado a veinte mil. A cada uno ellos le van a enviar un recuerdo con una selección de algunos de los quince jugadores de su plantilla (no necesariamente cinco). Eso sí, se autoimponen la siguiente condición: dadas dos alineaciones enviadas, los jugadores en común de ambas también deben formar otra de las selecciones elegidas. ¿Pueden hacerlo?
(Nota: la selección vacía también se admite.)
Solución:
Si nos olvidamos del contexto, nos preguntamos si es posible escoger veinte mil subconjuntos de otro con quince elementos de modo que la intersección de dos cualesquiera de ellos también es uno de los subconjuntos escogidos. Vamos a ver que es posible, probando por inducción, de hecho, que es posible formar tal colección de \(n\) alineaciones para todo \(0< n\leq 2^{15}=32768\).
Si \(n=32768\) es obvio que podemos conseguirlo, porque estamos tomando todas las posibles selecciones de los quince jugadores. Supongamos, pues, que para cierto \(r\leq 32768\), es posible realizar una colección \(\mathcal C\) de \(r\) selecciones, y probemos que podemos quedarnos con \(r-1\) cumpliendo la extraña condición sobre la intersección. Consideremos una de las alineaciones de \(\mathcal C\) de tamaño máximo (llamémosla \(A\)), y sea \(\mathcal{C}’:=\mathcal C\setminus{A}\). Cualesquiera otras dos selecciones \(B,B’\in\mathcal C\) no pueden contener a \(A\) por ser esta de tamaño máximo en la colección. Por tanto, tampoco la intersección \(B\cap B’\) la contendrá. En consecuencia, \(B\cap B’\in\mathcal C\setminus {A}=\mathcal{C}’\).
Tomando \(n=20000\) conseguimos lo que queríamos.
Otra manera equivalente de ver que es posible, según argumentan Marcos Jiménez y Manuel Zambrana en su solución, es tomar \(k_0\) como el mayor \(k\) tal que \(\sum_{j=0}^k {15 \choose j}\leq n\), (en nuestro caso, \(k_0=7\)) y quedarnos con todos los recuerdos con \(k_0\) jugadores o menos y los que falten hasta \(n\) de \(k_0+1\) jugadores. La intersección de dos conjuntos cualesquiera de ellos es un subconjunto de a lo sumo \(k_0\) elementos, que estará necesariamente entre los conjuntos elegidos.
En mi modesta opinión, acompañada de una formación académica antigua y no necesariamente puesta al día, considero que los enunciados de los dos últimos divertimentos, y digo dos, no estaban a la altura de claridad y «querer dejar claro qué se pegunta» de los anteriores.
No tengo ningún reparo en alabar las respuestas de los compis que las respondieron.
Espero se entienda este comentario en positivo.
Atentamente,
Juan Miguel
Gracias por el comentario, Juan Miguel, y perdón si no nos hemos explicado bien. Sin críticas (constructivas como la tuya) es imposible mejorar. Intentaremos que los siguientes enunciados sean más comprensibles.