Publicamos la solución al divertimento de la comparsa de caníbales de Cádiz. Gracias a Marcos Jiménez y Manuel Zambrana por la solución que nos han enviado.
Divertimento:
La comparsa de caníbales de Cádiz (CCC) tenía 30 miembros antes del martes de Carnaval, momento en el que celebran su cena festiva anual. Después de la cena se podía comprobar que en cualquier grupo de seis comparsistas de los que había antes había al menos un par de los que uno se había comido al otro. Probar que podemos formar una cadena de seis miembros de la CCC, cada uno habiendo comido al siguiente.
(Nota: no había miembros comidos por más de otro.)
Solución:
Antes de empezar con la solución propiamente dicha, incluiremos una discusión sobre el significado de «comer» en el enunciado del divertimento que puede ser contradictorio con las condiciones del problema.
El siguiente argumento se debe a Marcos Jiménez y Manuel Zambrana.
Supongamos que, en lo que sigue, «comer» o «devorar» significan comer directamente, sin intermediarios en una suerte de cadena trófica. Tomemos una partición de los treinta comparsistas formada por cinco grupos disjuntos de seis elementos cada uno. Se sigue, interpretando literalmente el enunciado, que en cada grupo existen comparsistas \(x\) e \(y\) tales que \(x\) se ha comido a \(y\). Sea \(A\) un conjunto de cinco pares del tipo anterior, con un par perteneciente a cada grupo. Denotemos por \(B\subset A\) el subconjunto de los cinco devorados de \(A\). Sea \(X\) el conjunto de todos los comparsistas y sea \(C=X\setminus A\).
Consideremos ahora el conjunto \(D=B\cup\{x\}\), con \(x\in C\), que tendrá seis elementos (pues \(x\notin B\)), por lo que uno de ellos se habrá comido a otro. Como los de \(B\) ya tienen su «comensal» y ninguno de ellos está en \(C\), necesariamente \(x\) es el que es comido, por alguno de los elementos de \(B\). Ahora bien, eso significa que todos los elementos de \(C\) son devorados por alguno de \(B\). Sin embargo, en aquel conjunto hay veinte elementos, por lo que de cualquier subconjunto de seis podemos encontrar a un par de devorado y devorador, no perteneciendo este último a \(B\). Eso es imposible, pues dos miembros no pueden comer al mismo.
En conclusión, debemos reemplazar nuestra definición de «comer». Diremos que «\(x\) se come a \(y\)» cuando se comen «con intermediarios», es decir, ambos elementos están en los extremos de una cadena trófica no vacía en la que cada elemento se come (directamente) al siguiente. Con esta definición, el razonamiento anterior no es contradictorio, y el siguiente (la solución en sí que teníamos) sigue siendo válido.
Fijémonos en los 30 miembros que había en la CCC. Diremos que un comparsista es un caníbal de profundidad \(0\) si nadie se lo comió (directamente). Por otro lado, un comparsista será un caníbal de profundidad \(k>0\) si se lo comió directamente otro que fue caníbal de nivel \(k-1\). Nótese que, por definición, ningún comparsista puede ser caníbal de profundidad mayor que \(30\) ni ningún miembro de la CCC se comió otro de la misma profundidad, porque el que es comido siempre tiene que ser de profundidad mayor que el que come.
El enunciado nos pide probar que había al menos un comparsista que fue caníbal de profundidad al menos \(5\), así que asumamos que solo hubo caníbales de profundidades \(0\), \(1\), \(2\), \(3\) y \(4\). Por el principio del palomar, habrá al menos seis caníbales de alguna de esas profundidades, y de esos seis hubo uno que se comió a otro, pero eso entra en contradicción con que fueran de la misma profundidad, y hemos terminado.
Dejar una contestacion