Ottaedro

[axpgn]

Partendo dalla "cima" di un ottaedro e percorrendo tutti gli spigoli una e una sola volta si torna al punto di partenza.
Quanti sono i diversi percorsi possibili?

Cordialmente, Alex

[Pachisi]

Non sono sicuro:

$32$?
Ho considerato lo sviluppo nel piano di un ottaedro. Vediamo che alcuni degli spigoli nello sviluppo in realtà coincidono nell'ottaedro, e poi si conta.

[orsoulx]

Ciao Pachisi
nel testo non viene chiarito se i vertici sono etichettati e quindi distinguibili, oppure no. Poco male: i percorsi diversi nei due casi stanno in rapporto 4. Anche nel caso con meno percorsi distinguibili (vertici non etichettati) mi pare che comunque il risultato debba essere ben più grande di quello che proponi. I soli percorsi più semplici da contare: giro dei vertici collegati al punto di partenza e poi spola fra il punto opposto e quello di partenza o, viceversa, prima la spola e poi il giro; sono già 24. I restanti sono sicuramente molti di più.
B.

[axpgn]

Eh, sì, son molti di più e tutti i vertici sono distinguibili ...

[Pachisi]

L'ho provato a fare tracciandoli (spero tutti)...

Me ne vengono $19$ senza rotazioni e/o simmetrie. Qualcuno conferma?

[axpgn]

La richiesta riguarda il numero di tutti i possibili "cammini" lungo gli spigoli di un ottaedro percorsi una e una sola volta, partendo dalla "cima" A e ritornandovi; tutti i vertici sono etichettati e conseguentemente anche gli spigoli sono tutti diversi e hanno due versi (AB è diverso da BA).

Cordialmente, Alex

[orsoulx]

@pachisi:
son convinto che siano pochi, ma senza giustificazioni risulta impossibile tanto cambiare idea quanto confutare le affermazioni.
Ciao
B.

[axpgn]

Nobody?

[orsoulx]

Per quel che mi riguarda ho già dato. Nel calcolare il numero di possibili circuiti euleriani mi perdo nei meandri del labirinto; potrei fare una stima grossolana e vaticinare più di 800. Potrei anche scrivere un programmino che lavori al posto mio, ma non ne ho voglia. Aspetto fiducioso nella tua bontà.
@Pachisi: se hai eliminato anche le simmetrie 19 torna anche a me. Però non mi pare lecito contare come uno solo due percorsi distinguibili perché di diversa chiralità.
Ciao
B.

[Pachisi]

Si, ho eliminato le simmetrie. Comunque servirebbe una dimostrazione. Anch'io mi blocco facendolo a mano...

[axpgn]

Sono $1488$.
Ho scomposto l'ottaedro (o meglio una sua schematizzazione) in figure più semplici fino al punto da poterne calcolare i percorsi possibili e poi sommando i risultati ottenuti.
Lo schema da cui sono partito è questo:

Cordialmente, Alex

[orsoulx]

Grazie Alex, un'altra delle tue spiegazioni illuminanti.
Ho capito dove sbagliavo: i miei grafi avevano archi curvi, adesso li raddrizzo e... voilà!
Ciao
B.

[axpgn]

Con calma, arrivo ... quando posso e se posso ...

Lo schema di partenza è questo:


Il punti di partenza e arrivo di ogni percorso è D.

Poniamo di iniziare a sciogliere il "nodo" A.

Di tutti i percorsi possibili lungo l'ottaedro, alcuni passeranno da A arrivando da B e proseguendo per C (e se teniamo conto del verso, altrettanti passeranno da A venendo da C verso B); ne consegue che ciascuno di questi percorsi ripasserà (o sarà passato, non è importante) da A venendo da E verso F (o viceversa).
Tutto ciò significa che, per quanto riguarda questi percorsi, posso immaginare il mio ottaedro come se non ci fosse più il nodo A e sostituendolo con una figura che che colleghi direttamente B con C ed E con F come questa:

Ripeto lo stesso ragionamento per le altre due possibilità (BE/CF e BF/CE) che portano a questo due figure:



La somma dei percorsi delle tre figure in cui ho scomposto l'ottaedro è uguale ai percorsi totali che posso fare sull'ottaedro.

Con questo metodo si può giungere a figure ancor più semplici delle quali si può calcolare direttamente il numero di percorsi.

È molto più difficile a dirsi che a farsi, garantisco ...

Cordialmente, Alex

[orsoulx]

Caro Alex,
se ti sei sentito spintonato da gnugnu hai frainteso: mi permetto di sollecitare una risposta solo quando qualcuno posta un problema di dubbia interpretazione o con dati incompatibili.
Prova a controllare chi ha lamentato la mancanza di interventi su questo problema. Io mi sono limitato a segnalarti, sorridendo, che il tuo penultimo veicolava un'informazione pari a zero. L'ultimo ne porta molta.
Grazie
B.

[axpgn]

Dai, pari a zero, no ... c'era la soluzione!

Non mi pareva si fosse lamentato nessuno ma ho controllato ... in effetti uno c'era: io ... ... vabbè, ma non era una lamentela, ho solo bussato per vedere se ci fosse ancora qualcuno ...

Cordialmente, Alex

P.S.: Mi accorgo solo ora che forse hai inteso quel "calma" come un invito rivolto a te ma non è così, era solo una descrizione del mio modo di procedere ...

[orsoulx]

"axpgn":Dai, pari a zero, no ... c'era la soluzione!

Se fosse sbagliata cosa sarebbe? Informazione negativa? Entropia? Già l'impietoso scorrer del tempo provvede a decimare neuroni e distruggere sinapsi; non infierire anche tu.
1488 non mi convince. Con Pachisi abbiamo 19 cicli euleriani, ciascuno dei quali può al massimo fornire $ 12 \cdot 4=48 $ percorsi diversi (non sempre lo sono) inizianti da A; più di 912 non ci stanno.
Ciao
B.

[axpgn]

"orsoulx":Se fosse sbagliata cosa sarebbe?

Ma sbagliata non è ...

Ho scomposto l'ottaedro come detto sopra e dopo diversi passaggi sono giunto a queste due figure:

Della prima figura ho $50$ istanze mentre della seconda ne ho $18$; dato che la prima è "percorribile" in $24$ modi diversi e la seconda in $16$ ottengo un totale di $1488=50 xx 24 + 18 xx 16$ percorsi diversi (sempre tenendo conto del verso di percorrenza).
Devo aggiungere che talvolta si presentano figure con un "loop" cioè un ramo che parte e termina sullo stesso nodo; in tal caso la "semplificazione" avviene eliminando il loop e raddoppiando le istanze della figura rimanente.
Riportare qui tutto il procedimento è troppo laborioso e lungo (non ho la pazienza e la capacità di Erasmus ... ), d'altra parte il metodo che ho seguito l'ho spiegato nei vari post.

Cordialmente, Alex

[orsoulx]

"axpgn":Ma sbagliata non è ...

Quando due risultati sono incompatibili almeno uno dei due è sbagliato.
Ciao
B.

[axpgn]

Come detto qui, ho scomposto l'ottaedro in tre figure più semplici ($a$, $b$ e $c$) tali che la somma dei loro percorsi fosse uguale al totale dei percorsi dell'ottaedro cioè $P=a+b+c$ e dato che, per i nostri fini, $a=b$ allora $P=2a+c$.

Proseguendo nella scomposizione dalla figura $a$ (o $b$) ottengo queste tre:
,
,
.

Dato che $a_2=a_3$ allora $a=a_1+2a_2$

Invece dalla figura $c$ ottengo queste tre:
,
,
.

Ai nostri fini è $c_1=c_3$ perciò $c=2c_1+c_2$, quindi $P=2a+c=2(a_1+2a_2)+2c_1+c_2=2a_1+4a_2+2c_1+c_2$.
Ma dato che $a_2=c_1$ allora $P=2a_1+6a_2+c_2$.

-Segue-

[axpgn]

Proseguo ...

Dalla figura $a_1$, eliminando il loop, ottengo questa:



Dobbiamo però raddoppiare le istanze perciò $a_1=2D$

Dalla figura $a_2$ abbiamo queste:

,
,
.

Quindi $a_2=2D+j$

Dalla figura $c_2$ abbiamo queste:
,
,
.

Quindi $c_2=j+2D$

Ricapitolando:
$P=2a_1+6a_2+c_2=2(2D)+6(2D+j)+(j+2D)=4D+12D+6j+j+2D$
$P=18D+7j$


-Segue-

[axpgn]

Proseguendo ulteriormente ...

Dalla figura $j$ eliminiamo il loop e diventa così:



La chiamiamo $J$ raddoppiando le istanze, per cui $j=2J$.

Dalla figura $D$ si ottengono queste:

,
,
.

Chiamando $K$ la prima e $J$ le altre (come detto sopra) abbiamo che $D=K+2J$.

Sostituendo in $P=18D+7j$ otteniamo $P=18(K+2J)+7(2J)=18K+36J+14J=18K+50J$

La figura $K$ può essere percorsa in $16$ modi diversi.
La figura $J$ può essere percorsa in $24$ modi diversi.

In definitiva $P=18K+50J=18*16+50*24=288+1200=1488$

C.V.D.

Cordialmente, Alex