Solución: Cambio de cromos

Publicamos la solución al divertimento Cambio de Cromos. En esta ocasión, Rafael Benzal, Fernando Carreño, Marcos Jiménez y Manuel Zambrana, Antonio Medinilla Garófano y David Ramos Orozco, Julio Ojeda Infantes y Pablo Puerto Muñoz y Javier Ribelles y Carmen Zuleta han resuelto el problema correctamente.

Divertimento:

Varios coleccionistas se reúnen en un evento para cambiar cromos, de modo que cada uno tiene al menos un cromo y a todos les falta algún cromo que tiene alguna otra persona.

¿Se puede asegurar que, bajo estas condiciones, hay al menos dos personas tales que a cada una de ellas le falte un cromo que sí tenga la otra?

Nota: suponemos que el número de coleccionistas reunidos es finito.

Solución:

Para cada persona \(A\), denotemos por \(C(A)\) al conjunto de sus cromos. La respuesta a la pregunta que se plantea es afirmativa. En caso contrario, dadas dos personas cualesquiera \(A\) y \(B\), se tendría que \(C(A) \subset C(B)\) o bien que \(C(B) \subset C(A)\). Por tanto, los conjuntos de cromos de los asistentes se pueden ordenar:
$$
\emptyset \neq C(A_1) \subset C(A_2) \subset \ldots \subset C(A_n).
$$
Se deduce que la persona \(A_n\) tiene todos los cromos que también tienen los demás, lo que contradice las condiciones del problema.

Marcos Jiménez y Manuel Zambrana han observado que es posible prescindir de la hipótesis que establece
que cada coleccionista tiene al menos un cromo, sin que ello altere las conclusiones. Suponer que a cada coleccionista le falta algún cromo que tiene alguna otra persona implica la existencia de coleccionistas (al menos dos) con colecciones no vacías. Sin embargo, en la reunión podría haber también coleccionistas que no tienen ningún cromo, sin incurrir en contradicciones (aunque lo normal cuando se asiste a un evento de cambio sea acudir con objetos para cambiar).

Además, algunos lectores del blog han resuelto el problema recurriendo a grafos dirigidos. Rafael Benzal ha propuesto la siguiente solución:

Sea \(G\) el grafo dirigido tal que los vértices son los coleccionistas y un arista \((V,V’)\) existe si \(V’\) tiene un cromo que \(V\) no tiene. La hipótesis de «a todos les falta algún cromo que tiene alguna otra persona» implica que de todos los vértices parte alguna arista. La conclusión «¿Se puede asegurar que, bajo estas condiciones, hay al menos dos personas que no tengan un cromo que sí tenga la otra?» se traduce en que existen dos vértices \(V\) y \(V’\) tales que \((V,V’)\) y \((V’,V)\) existen dentro del grafo.
Si tenemos dos vértices \(V\) y \(V’\) de manera que \((V,V’)\) pertenezca a \(G\) pero \((V’,V)\) no, quiere decir que todos los cromos que tiene \(V\) también los tiene \(V’\) y, por tanto, que todos los cromos que no tenga \(V’\) tampoco los tiene \(V\). En particular, sea \(V^{\prime\prime}\) tal que \((V’,V^{\prime\prime})\) existe; también ha de existir entonces \((V, V^{\prime\prime})\).
Ahora operemos por reducción al absurdo y supongamos que tenemos una configuración de coleccionistas y cromos tales que no existen dos vértices \(V\) y \(V’\) para los que existan simultáneamente \((V, V’)\) y \((V’, V)\). Consideremos un vértice cualquiera \(V\). Sabemos que existe otro vértice \(V’\) tal que \((V, V’)\) existe. Si \((V’,V)\) no existe, al menos ha de existir otro vértice \(V^{\prime\prime}\) tal que, como hemos indicado antes, \((V, V^{\prime\prime})\) y \((V’, V^{\prime\prime})\) sí existen. Nuevamente, si \((V^{\prime\prime}, V’)\) no existe, ha de existir otro vértice \(V^{(3)}\) al que \(V^{\prime\prime}\) esté conectado y, por tanto, todos los anteriores. De manera recursiva, podemos llevar este proceso hasta el último vértice que nos quede (suponiendo que el grafo es finito). Por construcción, todos los vértices están conectados a este último, y dado que por hipótesis este ha de estar conectado con algún otro, habría de existir una pareja y teniéndose la contradicción.

Sé el primero en comentar

Dejar una contestacion

Tu dirección de correo electrónico no será publicada.


*