Newsgroup: it.hobby.enigmi
Titolo: Le 3 case

Ecco il problema: ci sono 3 case (A,B,C) e 3 fornitori di servizi
(Gas,Luce e Telefono):
A   B   C
G   L   T
(bisogna disegnare il tutto su un foglio per capire meglio)
Come posso fare a collegare OGNI casa con OGNI fornitore SENZA che i
cavi o i tubi si incrocino?
byez,
Ugruk

...


E' incredibile come questo indovinello vine riproposto con periodicità cosi
precisa... penso che sia postato una volta al mese, con precisione quasi
perfetta... penso che ci sia qualche congiunzione astrale che porta il nuovo
arrivato di turno a postarlo ....
Non è una critica... perchè sono sicuro che molti nuovi "lettori" del
NewsGroup non l'avevano ancora letto ... era solo un osservazione...
__________________________________________
Se sei di buon umore, non ti preoccupare. Ti passerà.
e-mail : 
lu...@rub164.mi02.mi.interbusiness.it
__________________________________________
ugruk ha scritto nel messaggio


 Ecco il problema: ci sono 3 case (A,B,C) e 3 fornitori di servizi
Vecchi problema trito e ritrito.
E notoriamente irresolubile in due dimensioni.
Risparmiaci....
Ciao.
Mauro


wrote:

Scusate per il mio inizio.
Ammetto che sapevo dell'impossibilita' di questo problema, ma non sono
mai riuscito a trovare qualcuno che me lo dimostrasse.
Voi sapete farlo?
Penso che un po' di teoria sui grafi sia possibile dimostrarne
l'impossibilita', ma io non so da che parte iniziare ...
byez,
Ugruk

mbe'?
Nessuno mi aiuta? :(
Byez,
Ugruk
(4 e-mail replay remove "bastaspam")

 Nessuno mi aiuta? :(
Questo e' il famosissimo problema proposto da E. Dudeney " Utility
puzzle", chi non ci ha provato almeno una volta ? 
L'impossibilita' si puo' dimostrare cosi':
A,B,C sono le case e X,Y,Z i tre pozzi.
Supponiamo per il momento l'esistenza di sole 2 case e tracciamo il
grafo che le collega ai pozzi:
       A
     / | \
    /  |  \
   /   |   \ 
  X    Y    Z
  \ 1  | 2  /
   \   |   /  3
    \  |  /
     \ | /
       B
Possiamo spostare la posizione dei vari elementi o i percorsi delle
connessioni, avremo sempre un diagramma topologicamente equivalente,
cioe' abbiamo diviso il piano in 3 regioni indicate con 1,2,3.      
E' evidente che se ora piazziamo la casa C nell'area 1, potremo
collegarla solo ad X e Y, analogamente per le altre due regioni.
Quando ciascun nodo di un set di n punti e' collegato a ciascun nodo di
un secondo set di m punti, il tutto viene chiamato "Bigrafo completo".
Determinare il minor numero di incroci in un bigrafo completo e' impresa
piuttosto ardua, tanto da essere un problema ancora irrisolto. Esiste
una congettura data da Zarankiewicz nel 1954, il numero minimo di
incroci e' dato da:
[n/2][(n-1)/2][m/2][(m-1)/2]
dove il valore che si ottiene fra le parentesi quadre va arrotondato al
numero piu' basso.  
La formula e' stata verificata per n ed m < 7.
Come vedi il minimo numero di incroci per il bigrafo (3,3) e' = 1.
ciao :)dario

Luca (milano) wrote in message +ADw-6vkhf2+ACQ-jnf+ACQ-1+
AEA-nslave1.tin.it
+AD4-...
+AD4-E' incredibile come questo indovinello vine riproposto con periodicit+AOA- cosi
+AD4-precisa... penso che sia postato una volta al mese, con precisione quasi
+AD4-perfetta... penso che ci sia qualche congiunzione astrale che porta il
nuovo
+AD4-arrivato di turno a postarlo ....
+AD4-Non +AOg- una critica... perch+AOg- sono sicuro che molti nuovi +ACI-lettori+ACI- del
+AD4-NewsGroup non l'avevano ancora letto ... era solo un osservazione...
A questo punto urge una statistica +ADs-o)))
bye
Diego.

Toglimi la curiosità, sei il Dario Uri che scrive su MC?
Bye
Diego.

L'impossibilita' si puo' dimostrare cosi':
[cut]
1000 grazie !!!
Era un bel po' che mi arrovellavo inutilmente con i grafi :)
