OliForum Matematico

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

karlosson_sul_tetto ha scritto: 5) sono a scorrimento molto veloce ($\approx c^2$).

Pensi a quello che penso io?

I pedaggi sono tutti distinti vero?

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

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