Publicamos la solución al divertimento Postales. ¡Gracias a Alberto Castaño, Rafael Jiménez, Javier Linares y Cartesiano Caótico por vuestras respuestas!
Divertimento:
Cinco amigos salen de vacaciones al mismo tiempo y a diferentes lugares. Deciden que al llegar a su destino cada uno de ellos enviará una postal a tres de los restantes. ¿Es posible que cada amigo reciba postales de precisamente los tres amigos a los que él les envió las suyas? ¿Qué ocurriría en el caso de que fuesen seis los amigos?
Solución:
Representamos la correspondencia entre los amigos mediante un grafo. Cada vértice representa a uno de los amigos y las aristas representan las parejas de amigos que se escriben mutuamente. El siguiente grafo representa que A intercambia postales con B, D y E:
El grado de un vértice es el número de aristas que inciden en él. Todos los vértices del grafo del problema tendrían grado 3, porque cada amigo recibe postales de los tres amigos a los que él les envió las suyas.
En cualquier grafo, la suma de los grados de todos los vértices es igual al doble del número de aristas, porque cada arista añade 2 unidades a la suma los grados. En particular, esta suma es par. Por tanto, no es posible
que cada amigo reciba postales de los tres amigos a los que él les envió las suyas, porque generaría un grafo con cinco vértices de grado igual a tres, en el cual la suma de los grados es 15.
Esto sí es posible en el caso en que sean seis amigos:
Dejar una contestacion