Existen $n$ islas. En cada isla, quiero instalar una serie de carreteras (posiblemente $0$ ) que la conectan con otras islas. Cada carretera permite a una persona viajar en cualquier dirección entre exactamente dos islas. Diseño una red de carreteras. Le pido a mi amigo que me construya la red.
Sin embargo, mi amigo se equivoca y asegura que cada carretera sólo llevará pasajeros en una dirección, es decir, dos islas cualesquiera $a$ y $b$ que comparten una carretera, ésta sólo admitirá pasajeros de cualquiera de los dos $a$ a $b$ o $b$ a $a$ (pero no ambos). No importa qué planes le dé, cree que siempre puede dirigir el tráfico para impedir que ningún viajero regrese a su isla de origen una vez que se ha marchado. ¿Es posible su afirmación? Demuestre que hay una forma que debe funcionar, o demuestre que no existe tal estrategia.
Pensaba que esto tenía que ver con los grafos, donde el grafo tiene que ser acíclico para demostrar su afirmación, pero no estoy seguro de que sea así. Tal vez, ¿es posible demostrar su afirmación utilizando la inducción? Se agradece cualquier ayuda.
