Autostrade di pietra

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
karlosson_sul_tetto
Messaggi: 1452
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Autostrade di pietra

Messaggio da karlosson_sul_tetto »

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
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
AlexThirty
Messaggi: 217
Iscritto il: 20 giu 2015, 20:58

Re: Autostrade di pietra

Messaggio da AlexThirty »

karlosson_sul_tetto ha scritto: 5) sono a scorrimento molto veloce ($\approx c^2$).
Pensi a quello che penso io?
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.
bern-1-16-4-13
Messaggi: 78
Iscritto il: 23 mag 2015, 18:27

Re: Autostrade di pietra

Messaggio da bern-1-16-4-13 »

I pedaggi sono tutti distinti vero?
Testo nascosto:
Supponiamo per assurdo che alla fine il nostro grafo risulti diviso in almeno $3$ grafi disgiunti che numereremo da $1$ a $n$.
Definiamo strade di dogana tra $i$ e $j$ tutte le strade che collegano un elemento del sottografo $i$ con un elemento del sottografo $j$.
Andiamo a vedere la strada di dogana con pedaggio minore tra tutte, e diciamo $WLOG$ che è tra il grafo $1$ e il grafo $2$. Se questa è stata distrutta vuol dire che esiste un percorso hamiltoniano che passa per questa strada, ma per nessuna delle altre strade di dogana. Ma un percorso che rispetti queste caratteristiche può andare a toccare solo le città che si trovano nel grafo $1$ e quelle nel grafo $2$: assurdo.
Luca Nalon
Messaggi: 20
Iscritto il: 03 lug 2015, 16:15

Re: Autostrade di pietra

Messaggio da Luca Nalon »

AlexThirty ha scritto:
karlosson_sul_tetto ha scritto: 5) sono a scorrimento molto veloce ($\approx c^2$).
Pensi a quello che penso io?
Lo penso anch'io :mrgreen:

Per non dimenticare: viewtopic.php?f=31&t=15147
Rispondi