Tanto tempo fa, in un paese lontano lontano, c'era una monarchia assoluta e un gran numero di città. Alcune coppie di queste città sono collegate da un'autostrada, che hanno sempre queste caratteristiche:
1) sono a doppio senso di marcia
2) sono a pedaggio (con un prezzo diverso per ogni tratta tra quelle presenti)
3) per ogni coppia di città c'è (almeno) un percorso tra varie città e autostrade che permette di andare da una città all'altra
4) c'è almeno un cammino hamiltoniano tra le città (cioé un percorso che tocca ogni città esattamente una volta)
5) sono a scorrimento molto veloce ($\approx c^2$).
Il Re del paese individua tutti i possibili cammini hamiltoniani e per ognuno di essi, contrassegna l'autostrada presente nel cammino con il pedaggio più alto (può contrassegnare autostrade che ha già contrassegnato in precedenza). Dopo aver controllato tutti i cammini, fa chiudere tutte le autostrade che ha contrassegnato.
Dimostrare che per ogni terna di città A,B,C, almeno una delle seguenti affermazioni è vera:
1) Esiste un percorso da A a B
2) Esiste un percorso da B a C
3) Esiste un percorso da A a C
Autostrade di pietra
- karlosson_sul_tetto
- Messaggi: 1452
- Iscritto il: 10 set 2009, 13:21
- Località: Napoli
Autostrade di pietra
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
---
"Chissa se la fanno anche da asporto"
-
- Messaggi: 217
- Iscritto il: 20 giu 2015, 20:58
Re: Autostrade di pietra
Pensi a quello che penso io?karlosson_sul_tetto ha scritto: 5) sono a scorrimento molto veloce ($\approx c^2$).
Un bresciano esportato nel cremonese
-"Dal palazzo di giustizia di Catania o esci con più soldi di prima, o non esci proprio"
-"Baroni uscirebbe con un Win - Win".
Tutti si mettono a ridere, e allora intuisco che non aveva detto "Weed - Win" come avevo capito.
-"Dal palazzo di giustizia di Catania o esci con più soldi di prima, o non esci proprio"
-"Baroni uscirebbe con un Win - Win".
Tutti si mettono a ridere, e allora intuisco che non aveva detto "Weed - Win" come avevo capito.
-
- Messaggi: 78
- Iscritto il: 23 mag 2015, 18:27
Re: Autostrade di pietra
I pedaggi sono tutti distinti vero?
Testo nascosto:
-
- Messaggi: 20
- Iscritto il: 03 lug 2015, 16:15
Re: Autostrade di pietra
Lo penso anch'ioAlexThirty ha scritto:Pensi a quello che penso io?karlosson_sul_tetto ha scritto: 5) sono a scorrimento molto veloce ($\approx c^2$).
Per non dimenticare: viewtopic.php?f=31&t=15147