I percorsi sul cubo

[genny771]

Partendo da un vertice di un cubo quanti sono i percorsi lungo gli spigoli che attraversano una ed una sola volta ogni vertice?

[Sk_Anonymous]

Se ho capito il problema dico: nessuno, gli spigoli sono tutti di ordine dispari

[genny771]

Spigoli dispari?
Gli spigoli di un cubo ne sono 12.... http://it.wikipedia.org/wiki/Spigolo

[ViciousGoblin]

Non ha detto che gli spigoli sono dispari, ma che l'ordine di ogni spigolo è dispari...

[elgiovo]

Temo che si sia fatta confusione tra spigolo e vertice. Quelli cercati sono i famosi cammini hamiltoniani. Ad oggi non si conoscono condizioni necessarie perchè un grafo ne possieda, tuttavia i solidi platonici come il cubo sono hamiltoniani.

[Eredir]

"amelia":Se ho capito il problema dico: nessuno, gli spigoli sono tutti di ordine dispari

Però non mi sembra sia richiesto passare una volta per ogni spigolo, solo per ogni vertice.

Assegniamo ai vertici i punti $(0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1)$. Muoversi lungo gli spigoli vuol dire spostarsi di una distanza unitaria.
Allora un possibile percorso è $(0,0,0) -> (0,0,1) -> (1,0,1) -> (1,0,0) -> (1,1,0) -> (1,1,1) -> (0,1,1) -> (0,1,0)$.

[MaMo2]

Io, numerando i vertici ed utilizzando un diagramma ad albero, ho trovato 18 possibili percorsi.

[Eredir]

Confermo il risultato di MaMo.

L'ho verificato scrivendo questo programmino in Mathematica:

Module[{i, j, perm, len, count = 0},
  perm := Permutations[{{0,0,1},{0,1,0},{0,1,1},{1,0,0},{1,0,1},{1,1,0},{1,1,1}}];
  len := Length[perm];
  For[i = 1, i <= len, i++,
    If[Norm[perm[[i, 1]] - {0,0,0}] == 1,
      For[j = 1, j <= 6, j++,
        If[Norm[perm[[i, j]] - perm[[i, j + 1]]] != 1, Break[],
          If[j == 6, count++;]
        ]
      ]
    ]
  ]
  Print[count];
]

[genny771]

MaMo anche o ne ho trovati 18.
$3x2x2 + 3x2 = 18$

Non ho la risposta di questo quesito per questo vorrei confrontarmi con voi.

[qqwert]

Anche io ho trovato 18 ragionando come segue: fissato il vertice di partenza ho a mia disposizione 3 scelte possibili per il "primo passo"; fatto questo, per il secondo passo ho solo due possibilità, dato che la terza sarebbe quella di tornare indietro. Osserviamo a questo punto che a prescindere dal percorso scelto mi ritrovo sul vertice opposto a quello di partenza relativamente a una data faccia (che ovviamente dipende dal perorso scelto). Adesso ho due possibilità:
1) restare su tale faccia anche al terzo passo, così da percorrere tutti i vertici di tale faccia; a questo punto sono costretto ad andare su quella opposta in modo unico e da lì avrò due percorsi a disposizione per toccare tutti i vertici
2) andare sulla faccia opposta, sfruttando lo spigolo rimasto; da qui posso scegliere solo un percorso, cioè quello che mi porta al vertice opposto (parlando in termini di cubo) al vertice rimasto della faccia di partenza (da qui il percorso è poi determinato in modo univoco dalle regole); l'altro percorso non va bene perché mi "chiuderebbe" il vertice rimanente della faccia di partenza rispetto agli altri.

Ricapitolando ho:
- 3 scelte possibili al primo passo
- 2 scelte possibili al secondo passo
- 2 scelte possibili al terzo passo, di cui una che "permette" due percorsi, l'altra uno solo
Il numero totale di percorsi possibili sarà quindi 3*2*3=18

Pur essendo veramente molto stupido avendo a disposizione un cubo tra le mani (o in testa ) , diventa praticamente impossibile spiegare questo ragionamento a qualcun altro... scusate se vi ho fatto venire il mal di testa