lunedì 8 dicembre 2014

Varianti del problema dei 7 ponti di Königsberg

Se si rinuncia alla condizione che il punto di inizio e il punto finale debbano per forza coincidere, si potrà avere un cammino (ma non un circuito) euleriano anche nel caso in cui due vertici siano raggiunti da un numero dispari di spigoli. Indifferentemente, uno di essi rappresenterà il punto di partenza e l'altro quello di arrivo. Il problema originale dei 7 ponti di Königsberg  tratta di vertici generici, caratterizzati solo dai loro collegamenti, ma aggiungendo informazioni "urbanistiche e sociali", sono state proposte alcune simpatiche varianti al quesito in stile narrativo e descrittivo. Si ipotizza che sulla riva settentrionale sorgesse il castello del principe Blu e su quella meridionale quello del principe Rosso; sulla penisola si colloca il Vescovado e nell'isola centrale un'osteria. 
Per aiutarvi a visualizzare la situazione e a seguire i successivi sviluppi (risolvendo i quesiti) la città è stata ridotta a un grafo con i nodi colorati, attribuendo il bianco al Vescovo, ai castelli i colori dei rispettivi principi e rappresentando in arancione l'isola con l'osteria (disegno da Wikipedia) e ora comincia la storia. Era consuetudine di molti degli abitanti della città, prìncipi compresi, passare le serate all'osteria e quasi ogni notte qualcuno, già almeno brillo, scommetteva di essere in grado di attraversare i 7 ponti una volta ciascuno e tornare dagli amici. Alcuni, rientrati chissà come all'osteria, si vantavano di esserci riusciti senza però saper spiegare come, ma poco importava poiché comunque qualcuno avrebbe pagato e tutti avrebbero continuato a bere.

L'ottavo ponte del principe Blu
Il principe Blu, resosi conto dell'irrisolvibilità del problema, ne cambia un po' i termini e fa costruire di nascosto un ottavo ponte in modo che possa passarli tutti partendo dal suo castello e finendo all'osteria. Oltre a vantarsi della sua impresa potrà anche prendere in giro il suo rivale, il principe Rosso, poiché questi non può fare altrettanto iniziando dal suo castello.
Dove è stato costruito il ponte del principe Blu?

Il nono ponte del principe Rosso 
Il principe Rosso, non essendo disposto a subire passivamente l'affronto, decide quindi di far costruire un ulteriore ponte in modo da ribaltare la situazione. Ora è lui che può andare dal suo castello all'osteria passando per tutti i ponti e con questa aggiunta il principe Blu non potrà più fare altrettanto.
Dove è stato costruito il nono ponte del principe Rosso?

Il decimo ponte del Vescovo 
Ma a questo punto scende in campo il Vescovo che, irritato da questa stupida sfida che ha solo reso popolare l'osteria e ha fatto aumentare gli ubriachi che vanno in giro di notte per attraversare tutti i ponti, decide di far costruire un ultimo ponte che permetta a chiunque di passarli tutti, a partire da qualunque punto della città, e tornare a casa sobri, senza doversi fermare all'osteria.
Dove è stato costruito il decimo ponte del Vescovo?

Chi vuole verificare se ha assimilato il concetto, può risolvere i quesiti e disegnare i vari ponti, in successione. Gli impazienti possono facilmente trovare in rete la soluzione che comunque proporrò in un prossimo post.
Suggerimento: non perdete tempo procedendo per tentativi, ma ragionate in termini di nodi di grado pari e dispari e troverete rapidamente la soluzione di ciascun quesito.

Nessun commento:

Posta un commento