Newsgroup: it.hobby.enigmi
Titolo: disegnare casetta senza staccare la penna dal foglio

tutti sanno risolvere il problema della casetta disegnata con 8 segmenti 
senza staccare la penna o ripassare su un tratto gia' segnato.
Ma se la casetta ha ...4 tetti (uno per lato) per un totale di 14 segmenti 
come si risolve?

 ha scritto nel messaggio 
news:2x3sd.453878$35.19...@news4.tin.it...

E' impossibile con "4 tetti", e' una questione di parita'. Molto semplice 
invece farla con 1,2 e 3 tetti come si puo' facilmente verificare. Ancor 
piu' semplice verificare l' impossibilita' di disegnare in questo modo un 
quadrato con le due diagonali.
ciao
fulvio 

non mi ricordo a chi dobbiamo questo risultato (matematico del '700 se non 
ricordo male, e ai ponti che doveva attraversare durante la passeggiata 
pomeridiana) ma volevo solo precisare due cose...
Innanzitutto, il perchè... può sembrare un problema molto complesso 
stabilire se è possibile diseganre una certa figura senza staccare la penna 
dal foglio, in realtà è molto semplice... Se si ragiona in modo creativo e 
non nel "modo classico"... Basta infatti considerare tutti i "nodi" della 
figura che si vuole ottenere, ovvero quei punti per i quali passano più 
linee, e verificare che in ognuno di essi confluisca un numero pari di 
segmenti.
Se la figura che si vuole disegnare è un percorso chiuso (il punto di arrivo 
deve coincidere con il punto di partenza) risulta che per ogni strada che 
confluisce in un nodo ce ne deve essere una che ne esce.
Se la figura non è chiusa ma è una spezzata (punto di partenza e di arrivo 
diversi tra di loro), tutti i punti devono avere numero di strade pari 
tranne eventualmente due che possono averne un numero dispari. Chiaramente 
questi due punti devono essere punto di partenza e punto di arrivo: nel 
primo caso si ha almeno una strada in uscita dal punto partendo da esso, e 
in seguito ogni volta che si passa per quel punto si arriva per una strada e 
si parte per un'altra. Analogamente per il punto di arrivo.
L'enigma proposto non è risolvibile perchè ci sono ben quattro punti a cui 
sono connessi un numero di spari di strade e sono i punti alla base dei 
tetti.
Il caso del quadrato con le diagonali è ugualmente irrisolvibile perchè i 
punti nei quattro angoli hanno ciascuno un numero dispari di strade ad essi 
associate.
Il caso della "casina" con un tetto è risolvibile ma solo se i punti di 
partenza e di arrivo sono quelli alla base della casa: sono gli unici due 
punti con un numero di strade dispari ad essi associate dunque devono 
necessariamente essere partenza e arrivo.
La "casina" con due tetti diametralmente opposti è composta da soli punti a 
numero di strade pari e dunque è possibile risolvere il problema a partire 
da qualsiasi punto.
La "casina" con due tetti adiacenti è risolvibile solo considerando il punto 
in comune ai due tetti e l'unico punto non vicino ad alcun tetto della base 
come punti di partenza e di arrivo o viceversa perchè sono gli unici due 
punti a raccogliere un numero dispari di strade in tutta la figura.
La "casina" con tre tetti è anche essa risolvibile a patto di scegliere come 
punti di partenza ed arrivo i punti in comune a due coppie di tetti 
adiacenti. Sono gli unici due punti della figura serviti da un numero 
dispari di percorsi.
Tanto dovevo, e scusate gli eventuali errori ma è tardi e sono molto 
stanco...
Ste 

 "modo classico"...
grazie per l' ottima puntualizzazione, toglie via la ruggine a quelli come 
il sottoscritto :-)
ciao
fulvio 

 ricordo male, e ai ponti che doveva attraversare durante la passeggiata
Immanuel Kant e i famosi ponti di Konisberg (o qualcosa di simile)
Ciao

"Pronti Lee" scrive:

Veramente era un concittadino di Kant: Eulero, colui che ha rappresentato 
per la matematica quello che era Kant per la filosofia (se non di più).
GaS 

 per la matematica quello che era Kant per la filosofia (se non di più).
Eccoli qua i 7 ponti Königsberg:
.
.
.               ________| |_______| |_________________| |_______
.              |  ______| |_______| |_______   _______| |_______
.              | |      | |       | |       | |       | |
.              | |                          | |
.              | |                         _|_|_
.              | |                         _____
.              | |                          | |
.              | |                          | |
.______________| |______| |_______| |_______| |
._______________________| |_______| |_______  |
.                       | |       | |       | |
.                                           | |
.                                          _|_|_
.                                          _____
.                                           | |
.                                           | |
.                                           | |
.
.
Bisogna passare sui 7 ponti una volta sola in un unico
percorso. Per vedere l'ascii-art usare caratteri fissi.
                     ((^__^))
Ciao!!!
Livio
_______________________

 senza staccare la penna o ripassare su un tratto gia' segnato.
Molto piu' complesso e' contare in quanti modi distinti puo' essere fatto.

 ha scritto nel messaggio 
news:Rstsd.27219$C94....@tornado.fastwebnet.it...

Già... e così su due piedi mi viene da dire che un buon modo (forse il 
migliore?) per farlo è costruire un albero binario che esplorando tutti i 
casi ci aiuta a tener conto di quante e quali soluzioni sono possibili.
Così come per l'algoritmo di risoluzione dei circuiti hamiltoniani, si 
possono riconoscere configurazioni che ci permettono di stabilire se un ramo 
dell'albero binario è "secco" prima di aver esplorato l'intero sottoalbero, 
permettendoci di ottimizzare l'algoritmo nel tempo.
Per quanto riguarda la casina da disegnare senza staccare mai la penna dal 
foglio, il risolutore era proprio Eulero, la città era Konigsberg e il fiume 
che giustificava la presenza dei ponti era il Pregel. Per chi non conoscesse 
la storiella, i ponti di Konigsberg sul fiume Pregel offrivano panorami 
stupendi, e la popolazione di Konigsberg era solita fare passeggiate che le 
permettessero di godere del maggior numero di quei bei panorami. Nessun 
cittadino però era mai riuscito a compiere un percorso chiuso (essì, partiva 
da casa sua e sperava di ritornarci, prima o poi ;-P) che gli permettesse di 
visitare tutti i ponti senza mai passare due volte per lo stesso ponte. 
Eulero era molto famoso per la brillantezza delle sue decisioni, e quando 
nel 1736 gli fu chiesto da un concittadino a nome della popolazione di 
risolvere il problema, lui formulò quanto ho già detto in un altro post...
Per chi si volesse cimentare col problema originale, ecco come ottenerne la 
figura...
* si traccino due rette parallele orizzontali: quelle sono le sponde del 
fiume Pregel.
* si disegnino nel mezzo del "fiume" due isolotti, equidistanti dalle sponde 
e "uno dopo l'altro" come se fossero in fila
* si congiungano la riva "nord" del fiume Pregel e l'isolotto "ovest" con 
due segmenti paralleli di colore diverso in modo da essere distinti dal 
resto della figura finora tracciato
* analogamente, si congiunga la riva "sud" del Pregel con l'isolotto "ovest" 
con due segmenti paralleli dello stesso colore di quelli del punto 
precedente
* si tracci un unico segmento dello stesso colore dei segmenti finora 
tracciati che congiunge i due isolotti tra di loro
* si tarcci un segmento colorato anche tra la riva "nord" del Pregel e 
l'isolotto "est"
* infine si tracci un segmento colorato tra la riva "sud" del Pregel e 
l'isolotto "est"
Chiaramente i segmenti colorati indicano i ponti e si chiede se è possibile 
percorrere tutti i ponti una sola volta con un percorso chiuso a partire da 
un punto a scelta della "cartina" di Konigsberg appena tracciata. 

 ha scritto nel messaggio 
news:Rstsd.27219$C94....@tornado.fastwebnet.it...

Perdonatemi se dico una stupidaggine, il che e' probabile, ma qualche 
reminiscenza gardneriana (il quadrato di quadrati) mi fa nascere l' ipotesi 
che si possa trasporre la faccenda sul campo delle reti elettriche (cosa che 
per me e' vicino all' arabo). E' solo un suggerimento per i piu' 
competenti...
ciao
fulvio 

 che si possa trasporre la faccenda sul campo delle reti elettriche 
Non credo siano qui applicabili.
Pero' il metodo c'e'.
Gaston Tarry "Suppression sucessive des carrefour".
Lo invento' per risolvere un problema complesso il cui enunciato era:
  "In quanti modi una serie di domino formata dai 28 pezzi da 0-0 fino a 
6-6 puo' formare una linea?" (seguendo naturalmente la regola del domino 
dove 2 tessere possono essere contigue solo se presentano lo stesso valore)
Nel 1871 fu pubblicata a Milano una prima soluzione di un certo Reiss 
che in ben 58 pagine di calcoli contava 7.959.229.931.520 possibili casi.
Nel 1886 Gaston Tarry con una idea veramente ingegnosa, confermava il 
risultato di Reiss.
Praticamente Tarry noto' che il numero dei modi in cui le 21 non-doppie 
tessere possono essere sistemate ad anello e' uguale al numero di  vie 
unicursali su un grafo completo ettagonale. Disegnate un ettagono 
regolare con tutte le possibili diagonali numerando ciascun vertice con 
le cifre da 0 a 6 allora ogni linea congiungente 2 vertici rappresenta 
la corrispondente tessera. E' chiaro che un tracciato continuo 
sull'ettagono corrisponde ad una sistemazione circolare delle 21 tessere
Tarry trovo' (col metodo ingegnoso che ancora non vi dico) che le 
suddette vie unicursali sono 129.926.320, le rimanenti 7 doppie-tessere 
possono essere aggiunte in ogni anello in 37 modi. Infine ogni anello 
puo' essere aperto in uno qualsiasi dei 28 punti. Ne consegue:
28*37*129.976.320 = 7.595.229.931.520 in perfetto accordo con i 
risultati di Reiss.
La stessa tecnica puo' essere applicata al computo (molto piu' semplice) 
dei possibili percorsi sulla nostra casetta.
Rimboccatevi le cotenne e cercatevi la strada giusta....

 i ponti di Konigsberg sul fiume Pregel.... 
Credo che qui sia proprio di pubblico dominio.
Molti pero' forse non sanno che nelle "Memoire des Ponts de la Pregel" 
Eulero non menziona il fatto che un tracciato con 2 nodi dispari possa 
essere percorso, questo fu notato in seguito da Clausen.
Vi e' poi un altro teoremino di Tremaux che recita cosi':
"Ogni tracciato continuo puo' essere disegnato con un solo tratto e 
passante 2 volte su ciascuna linea"
Attenzione !! udite udite dopo 120 anni la soluzione dei ponti e' stata 
trovata.
Una volta raggiunta una parte del fiume basta semplicemente farsi una 
bella passeggiata ed aggirare la fonte del Pregel per portarsi dalla 
parte opposta e concludere il giro.

 opposta e concludere il giro.
Bellissima!!
:o)
Ciao,
GaS 

Non ho mai sentito parlare dei quadrati di quadrati e di come questi possano
essere applicati alle reti elettriche...
Di sicuro è un problema di ricerca operativa classica... dove per ricerca
operativa si intende l'individuazione dell'algoritmo che risolve "meglio"
(in meno tempo, ad esempio, o con meno spreco di un'altra risorsa
quantificabile , come il tempo appunto) un problema di una certa difficoltà.
Secondo me, il problema in letteratura che più si avvicina a questo, è
quello dei circuiti hamiltoniani...
Questo tipo di circuiti (l'elettricità non centra, circuito è inteso come
percorso chiuso) è diventato famoso come "gioco da tavolo" di matematica
ricreativa, prodotto da Lord Hamilton a metà del 1800...
Si dice circuito hamiltoniano un circuito chiuso costruito a partire da
certi punti detti nodi badando a massimizzare (o minimizzare) una certa
proprietà del circuito stesso, senza mai passare due volte per lo stesso
nodo. Ad esempio, dato un insieme di nodi e le distanze relative tra ogni
nodo e gli altri nodi del sistema, il classico circuito hamiltoniano è quel
circuito chiuso che passa per tutti i nodi una sola volta e che, nel
complesso, è più corto degli altri possibili. Va da se che, dato un sistema
qualsiasi di nodi, potrebbe non esistere il circuito hamiltoniano ad esso
associato o potrebbero esistere più circuiti hamiltoniani equivalenti in
termini di distanza percorsa.
(nb: se il percorso non è in qualche modo orientato ed esiste un circuito
hamiltoniano che risolve il problema, allora ne esiste almeno un altro ad
esso equivalente e che risulta essere lo stesso circuito percorso in
direzione opposta)
A differenza dei circuiti hamiltoniani, i nostri grafici possono percorrere
uno stesso nodo più volte, ma lo stesso segmento non può essere percorso più
di una volta. A occhio e croce mi vien da dire che effettuando una
"trasformazione" da segmenti (di grafici "a casetta") a nodi (di circuiti
haltoniani), sia possibile applicare l'algoritmo per l'esplorazione dei
circuiti hamiltoniani al nostro problema. Il nostro problema è una versione
"rilassata" del problema di Hamilton, perchè non ci viene chiesto di trovare
la soluzione che ricopra il nostro grafico con i segmenti più corti, ma ci
viene chiesto di enumerare tutte le soluzioni... Sicuramente il nuovo
algoritmo richiederà più tempo del precedente. Tuttavia, essendo il nuovo
problema più specifico del problema di Hamilton, immagino si possano trovare
leggi (anche empiriche) che permettano di scartare a priori quei rami che
non porteranno a soluzione. Un esempio relativo al problema di Hamilton,
tanto per far capire cosa intendo: l'albero binario associato al problema di
Hamilton ci permette di esplorare il problema in modo intelligente. Quando
stabiliamo che un certo segmento deve far parte della soluzione, in pratica
uniamo un punto che già fa parte della soluzione, ad un nuovo punto che
ancora non ne fa parte. Sapendo che non è possibile ripassare per lo stesso
nodo più volte, è possibile eliminare dall'insieme delle "mosse" future
tutte quelle che prevedono di passare per il nuovo nodo scelto, perchè
sappiamo che quelle mosse sono diventate illegali dopo la nostra scelta. E
analogamente si potrebbe fare per i nostri grafici a casetta.
Purtroppo non ho il tempo di cimentarmi col problema, ma spero che queste
indicazioni abbiano fornito uno spunto per chi volesse confrontarsi con la
cosa. Se volete più dettagli sulla teoria hamiltoniana penso sia sufficiente
fare una ricerchina in Google... Dovrebbero saltare fuori molti risultati,
se non altro di molti atenei in relazioni a corsi di Ricerca Operativa...
Ciao,
  Ste

 Molto piu' complesso e' contare in quanti modi distinti puo' essere fatto.
Qualcuno conferma 21 percorsi diversi?
Per evitare fraintendimenti: io ho considerato la figura
  /\
 /  \
o----o
|\  /|
| \/ |
| /\ |
|/  \|
o----o
ho considerato distinti i due rami superiori ed ho considerato uguali due 
percorsi speculari.
Sinceramente il risultato viene da una becera ricerca esaustiva, non riesco 
ad intraveder un metodo piů "ricercato" :o)
GaS 

 percorsi speculari.
Io conto 44 percorsi da "a" a "b" cioe' 88 in tutto.
Considerando pero' anche il nodo
all'incrocio delle due diagonali, come ammesso dal problema,
diventano 120 in un senso cioe' 240 in tutto (salvo errori od ommissioni).

 diventano 120 in un senso cioe' 240 in tutto (salvo errori od ommissioni).
Non ho mai considerato il nodo centrale come appartenente al tutto, 
considerandolo in effetti il numero totale di percorsi sale di molto e la 
ricerca esaustiva a carta e matita è troppo onerosa. A questo punto penso 
proprio che serva il metodo di cui hai parlato in un altro post, domani ho 
un viaggio di 5 ore in treno, chissà che il dondolio dei vagoni ed il tempo 
libero non portino consiglio.....
Ciao,
GaS
P.S.: Da un problema cosi banale e arcinoto ne può sempre venire fuori 
qualcosa di nuovo ed interessante, non me lo sarei mai aspettato: grazie 
Dario!! e grazie anche a Danger che a riproposto il problema. 

Vedo se mi riesce di spiegare il metodo.
Vado col caso semplificato. Casetta con 4 nodi.
Cerco il totale dei percorsi da "a" a "b" che chiamero' S.
    ___
   /   \
  /     \
O-------O
|\     /|
|  \ /  |
|  / \  |
|/     \|
O-------O
a       b
Il metodo consiste essenzialmente nell'eliminare un nodo ad ogni 
passaggio, fintanto che il numero dei nodi si riduce a 2 dove il computo 
diventa semplice, ma andiamo per gradi.
Il nodo in alto a sx puo' essere scomposto in 3 Casi che chiamero' A,B,C
-----------------------------------------------------------------------
Caso A = La linea verticale che parte da "a" continua verso il tetto.
    ___
   /   \
  /     \
|  /----O c
| |    /|
|  \ /  |
|  / \  |
|/     \|
O-------O
a       b
Se le linee le consideriamo un po' elastiche possiamo sostituire questo 
grafo con quest'altro equivalente:
      c
      O
    // ||
   //  ||
  //   ||  Grafo D
//    ||
O-----O
a      b
--------------------------------------------------------------------------
Caso B = La linea verticale che parte da "a" prosegue verso "c"
   _____
  /     \
/       \
\|-------O c
  |\    / |
  |  \ /  |
  |  / \  |
  |/     \|
  O-------O   Che semplificato corrisponde topologicamente al Grafo D
a        b
---------------------------------------------------------------------------
Caso C = La linea verticale che parte da "a"  prosegue verso "b"
    ___
   /   \
   \    \
|\ \----O c
| \    /|
|  \ /  |
|  / \  |
|/     \|
O-------O
a       b
Che semplificandolo diventano 3 linee che congiungono "a" con "b" una 
delle quali presenta un loop:
        /\
     ___\/___
    /   c    \
a O----------O b   Grafo E
    \________/
-------------------------------------------------------------------------
Praticamente abbiamo separato il nostro problema originario in 3 
percorsi piu' semplici, e' evidente che la somma di tutti i percorsi
possibili sui 3 subgrafi e' uguale a S.
Posso scrivere  D+D+E=S
Nel grafo E partendo da "a" ho 3 scelte, e 2 al ritorno. 6 percorsi in 
tutto, ma il loop lo posso disegnare nei 2 sensi. E = 6*2 = 12
Eliminando con lo stesso procedimento il nodo "c" nei Casi A e B
(lascio a voi questo compito) ci ritroveremo con 4 subgrafi di questo tipo:
     ________
    /        \
a O----------O b
    \________/     Che generano ciascuno 6 soluzioni. 6*4 = 24
e due subgrafi di questo tipo:
    /\_________/\
    \/a       b\/ Che generano ciascuno 4 soluzioni. 4*2 = 8
Totale 12+24+8 = 44.
Che diventano 88 considerando che la figura puo' essere disegnata da "b" 
verso "a".
Con lo stesso principio scomponendo anche il nodo formato dalle 2 
diagonali, si trovano facilmente i 120 (240) modi di disegnare la famosa 
casetta.