Olimpiada All-Russian, primer problema del primer día del grado 9
En un país, algunas ciudades están conectadas por vuelos en avión, no necesariamente en los dos sentidos (no hay más que un vuelo entre dos ciudades determinadas).
Decimos que una ciudad A está disponible desde una ciudad B, si podemos volar de B hasta A, tal vez haciendo varias escalas.
Se sabe que para cada par de ciudades P y Q, existe una ciudad R desde la que tanto P como Q están disponibles.
Prueba que existe una ciudad A desde la que todas las ciudades están disponibles.
Solución:
La respuesta es sencilla, una vez que se entiende bien.
Veamos que es cierto en casos pequeños. Debe tratarse de, al menos, tres ciudades, puesto que para menos casos no es aplicable el razonamiento.
Con tres ciudades, está claro que si tomamos dos de ellas, existe una desde las que ambas son accesibles, es decir, desde esa tercera ciudad, diferente de las otras dos, ambas son accesibles, luego desde esa ciudad todas las restantes son accesibles.
En este caso, ni siquiera es necesario aplicar inducción estrictamente. Supongamos que M es una ciudad desde la que el número de ciudades accesibles es lo mayor posible (en lenguaje matemático, este elemento se denomina maximal).
A partir de ahora se razona por reducción al absurdo, esto es, suponemos que algo es cierto y llegamos a una situación imposible. Como conclusión, lo que hemos supuesto no es cierto.
Veamos que es imposible que haya una ciudad inaccesible desde M (la ciudad maximal).
Si existiera esa ciudad, llamémosla X, inaccesible desde M, al tomar P y Q como M y X respectivamente, sabemos que existe una ciudad R desde la que X y M son accesibles, pero eso significa que desde R es accesible cualquier ciudad que lo fuese desde M, ya que podríamos hacer transbordo en M y también es accesible X, cosa que es imposible, pues se supone que no es posible tener más ciudades accesibles que M (recuerda que M era maximal).
Luego desde M todas las ciudades son accesibles, y es la que buscábamos para probar el enunciado.