En el país de Siete hay 15 ciudades, cada una de las cuales está conectada, al menos, con otras 7. Se plantea la siguiente duda, ¿se puede viajar de una ciudad cualquiera hasta otra pudiendo pasar a través de otras ciudades? Ayuda al país de Siete y decide si se puede o no.
La solución algo más abajo.
SOLUCIÓN:
Vamos a demostrar que sí se puede, suponiendo lo opuesto para llegar a una contradicción. Consideramos 2 ciudades cualesquiera y supongamos que no hay camino alguno que las una. Esto significa que no hay una secuencia de carreteras que conecten las dos ciudades, tal que el fin de una coincida con el comienzo de otra. Se sabe que cada una de las dos ciudades está conectada al menos con otras 7. Esas 14 ciudades deben ser distintas: si coincidieran, habría un camino a través de ellas (o de ella) que conectaría las 2 ciudades. Añadiendo a estas 14 las 2 iniciales, al menos deberíamos tener 16 ciudades diferentes, lo cual, es una completa contradicción por lo que obligatoriamente el enunciado es verdadero.
No hay comentarios:
Publicar un comentario