|
| Precedente :: Successivo |
| Autore |
Messaggio |
Zeus
Amministratore
Registrato: 21/10/00 01:01
Messaggi: 12777
Residenza: San Junipero
|
 Inviato: 29 Lug 2008 15:48 Oggetto: Il turista meticoloso |
 |
|
| Un turista si reca in una nazione straniera e vuole visitare a fondo tutte le n città di tale nazione. Da ciascuna città si può raggiungere (in autobus oppure in treno) ciascuna altra città della nazione tramite un collegamento diretto: ma le città che sono collegate tra loro da una linea di autobus non sono collegate tra loro da una linea ferroviaria, e viceversa. Il nostro turista vuole passare da tutte le città una e una sola volta, e inoltre non vuole cambiare mezzo di trasporto più di una volta: in pratica vuole fare una parte del viaggio in autobus e la restante parte in treno, o viceversa. Considerato che il turista può scegliere a proprio piacimento il punto di partenza e l'itinerario, riuscirà nel suo intento? Dimostratelo. |
|
| Top |
|
 |
ulisse
Dio maturo
Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)
|
| Inviato: 06 Ago 2008 15:43 Oggetto: |
|
|
| Citazione: | Secondo me sì, il desiderio del turista può essere soddisfatto per ogni n e per qualsiasi composizione della rete auto-ferroviaria.
Lo si dimostra per induzione ovvero verificando che se è possibile organizzare un percorso che soddisfa i requisiti del turista in una rete di collegamento tra n città allora è anche possibile organizzare un tale percorso aggiungendo in modo qualsiasi una ulteriore città alla rete.
Dimostrato ciò si osserva che per n=2 il problema ha soluzione e quindi, per induzione, ha soluzione per qualunque valore di n.
Il problema mi suona vagamente familiare, soprattutto dopo aver pensato che la strada buona poteva essere quella dell'induzione, ma non riesco a determinare se e dove ne ho sentito parlare.
Ma ecco la dimostrazione dell'induzione.
Non è rigorosa ma credo stia in piedi.
Rappresentiamo le città con dei punti su un foglio e i collegamenti con dei segmenti.
Per distinguere tra treno e autobus potremo usare una linea continua per il treno e tratteggiata per l'autobus.
I punti possono essere disegnati su un foglio in modo qualsiasi non essendo necessario, per questioni di topologia, rispettare l'esatta dislocazione sul territorio.
Nulla ci vieta, quindi, di disporre le n città sui vertici di un poligono di n lati.
Non è indispensabile ma facilita l'immaginazione.
I collegamenti saranno quindi rappresentati da lati e diagonali del poligono.
La disposizione delle città sui vertici può essere qualsiasi. Ovviamente cambiando la disposizione delle città bisogna anche agire di conseguenza sui collegamenti.
Il punto cruciale consiste nell'osservare che se per un gruppo di n città esiste un tragitto che le collega rispettando le richieste del turista allora è possibile collocare le città sui vertici in modo che tale tragitto giaccia interamente sul perimetro del poligono e, di più, in modo che tutti i lati percorsi dallo stesso mezzo siano contigui.
Mi sembra meglio proseguire con un esempio.
Supponiamo di avere una nazione con le 6 città A, B, C, D, E, F.
L'ipotesi induttiva dice che esiste certamente un tragitto con le caratteristiche richieste.
Sia esso AFECBD dove la parte AFEC è percorsa, che so, in treno e la parte CBDA in autobus. (che la tratta DA sia percorribile in autobus o in treno in realtà non ci interessa perché non è richiesto il ritorno al punto di partenza ma dopo servirà saperlo).
Allora posso disegnare il poligono depositando le città esattamente in questo ordine AFECBD.
I lati AF, FE, EC saranno a linea continua mentre i lati CB, BD e DA a linea tratteggiata.
Le diagonali non ci interessano. Siano quel siano.
Ora dobbiamo aggiungere la nuova città, detta G.
Per integrare la rete di collegamento potremo disegnare G come vertice di una piramide avente AFECBD come poligono di base.
Le nuove tratte saranno dunque gli spigoli laterali della piramide.
Essi, come gli altri, saranno disegnati a linea o continua o tratteggiata.
Guardiamo il perimetro del poligono di base.
Dai vertici F, E, B, D escono due lati dello stesso tipo (entrambi percorribili col medesimo mezzo).
Ma nei vertici A e C abbiamo la situazione mista ovvero da un lato autobus e dall'altro treno.
Ciò significa che qualunque sia il mezzo utilizzato per percorrere GA, il turista partito da G e arrivato in A potrà proseguire la sua visita senza dover effettuare cambi oltre quello già programmato.
Supponiamo che GA sia in treno, allora il nuovo percorso sarà semplicemente GAFECBD (GAFEC in treno e CBD in autobus).
Se GA fosse in autobus allora il nuovo percorso sarebbe GADBCEF (GADBC in autobus e CEF in treno). |
|
|
| Top |
|
|
ulisse
Dio maturo
Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)
|
| Inviato: 06 Ago 2008 18:05 Oggetto: |
 |
|
| Citazione: | In pratica, avendo 5 città, una rete di collegamento tipo questa
(notare la colorazione dei segmenti: in nero per indicare un tipo di mezzo e in rosso l'altro) può sempre essere rigirata così.
In questa seconda disposizione è evidente che per percorrere uno dei possibili tragitti soluzione (ad esempio EACBD) basta restare sul perimetro.
Ed è anche facile vedere che una nuova città, sia essa G, può essere collegata in qualsiasi modo perché se il collegamento GE è rosso il percorso partirà da G e, transitando per E andrà verso D
mentre se il collegamento GE è nero, dopo il transito per E, si andrà verso A |
|
|
| Top |
|
|
|
|
Non puoi inserire nuovi argomenti
Non puoi rispondere a nessun argomento
Non puoi modificare i tuoi messaggi
Non puoi cancellare i tuoi messaggi
Non puoi votare nei sondaggi
|
|
FAQ
Cerca
Lista utenti
Gruppi
Registrati
Profilo
Messaggi privati
Log in
