OliForum Matematico

questa mi è venuta in mente col cubo di rubik ( e io non conosco la soluzione):
qual è il numero minimo di mosse per essere certi che con questo numero di mosse o con un numero più piccolo si possa risovere lo stesso se i cubetti di esso sono disposti in un modo qualsiasi?
mi spiego meglio: indichiamo con "m" il numero minimo di mosse per risolvere il cubo quando è in una certa configurazione. Al variare delle configuazioni qual è il valore massimo di "m"?
quest'altra domanda dovrei metterla su combinatoria ma ormai.... in quanti modi si può combinare il cubo? io avevo pensato così: 3^8*8!*2^12*12! perchè i centrali sono amovibili e quindi costituiscono un "sistema di riferimento", gli angoli possono permutare le posizioni tra loro e ognuno di essi si può girare in 3 modi anche gli spigoli possono permutarsi tra loro e ognuno si può girare in 2 modi. Facendo così mi ridà circa 5,19 *10^20 mentre secondo wikipedia sono 43.252.003.274.489.856.000[/tex]

sgiangrag ha scritto:questa mi è venuta in mente col cubo di rubik ( e io non conosco la soluzione):
qual è il numero minimo di mosse per essere certi che con questo numero di mosse o con un numero più piccolo si possa risovere lo stesso se i cubetti di esso sono disposti in un modo qualsiasi?
mi spiego meglio: indichiamo con "m" il numero minimo di mosse per risolvere il cubo quando è in una certa configurazione. Al variare delle configuazioni qual è il valore massimo di "m"?

Mi pare sia un problema aperto. I programmi più efficienti per la ricerca di soluzioni "corte" arrivano a circa una ventina di mosse nelle configurazioni più sfigate. Tempo fa ero arrivato a una pagina che ne parlava seguendo un paio di link, probabilmente con un abile uso di google riesci a ritrovarla.

quest'altra domanda dovrei metterla su combinatoria ma ormai.... in quanti modi si può combinare il cubo? io avevo pensato così: 3^8*8!*2^12*12! perchè i centrali sono amovibili e quindi costituiscono un "sistema di riferimento", gli angoli possono permutare le posizioni tra loro e ognuno di essi si può girare in 3 modi anche gli spigoli possono permutarsi tra loro e ognuno si può girare in 2 modi. Facendo così mi ridà circa 5,19 *10^20 mentre secondo wikipedia sono 43.252.003.274.489.856.000[/tex]

Hai impostato bene il calcolo, ma stai contando anche alcune configurazioni irraggiungibili: per esempio, non riuscirai mai ad arrivare nella posizione "tutto il cubo fatto, tranne uno spigolo girato nel verso sbagliato". Ci sono alcuni "invarianti" che tutte le mosse conservano e che bisogna considerare. Il tuo calcolo dovrebbe essere sbagliato di un fattore 12, nei dettagli:
-l'orientazione dell'ultimo spigolo è obbligata
-l'orientazione dell'ultimo angolo è obbligata
-le permutazioni di angoli e spigoli devono avere la stessa parità.
Hint per la dimostrazione:
1) metti una vagonata di notazioni in modo da rappresentare un orientamento del cubo come (permutazione degli angoli, permutazione degli spigoli, sequenza di 12 zeri o uni che rappresenta l'orientamento degli spigoli, sequenza di 8 zeri, uni o dui che rappresenta l'orientamento degli angoli). Ti scrivi cosa fanno le nove mosse "elementari" nella tua notazione, verifichi che tutte rispettano gli invarianti che ti ho detto. Ma non ti consiglio di metterti davvero a farlo.
2) Tutte le configurazioni che rispettano questi vincoli si raggiungono: se sai come si risolve un cubo dovresti riuscire a "costruire" facilmente anche un algoritmo che ti porta in una qualunque delle configurazioni che rispettano questi vincoli.

ciao,
-f

diviso 12 ridà esattamente...

fph ha scritto: -l'orientazione dell'ultimo spigolo è obbligata

e quindi è diviso 2

fph ha scritto: -l'orientazione dell'ultimo angolo è obbligata

e quindi è diviso 3

fph ha scritto: -le permutazioni di angoli e spigoli devono avere la stessa parità.

e questo non ho capito che significa... potresti spiegare? cmq farà diviso 2 (12=2*3*2)

fph ha scritto: metti una vagonata di notazioni in modo da rappresentare un orientamento del cubo come (permutazione degli angoli, permutazione degli spigoli, sequenza di 12 zeri o uni che rappresenta l'orientamento degli spigoli, sequenza di 8 zeri, uni o dui che rappresenta l'orientamento degli angoli). Ti scrivi cosa fanno le nove mosse "elementari" nella tua notazione, verifichi che tutte rispettano gli invarianti che ti ho detto. Ma non ti consiglio di metterti davvero a farlo.

non lo farò... grazie mille

sgiangrag ha scritto:

fph ha scritto:-le permutazioni di angoli e spigoli devono avere la stessa parità.

e questo non ho capito che significa... potresti spiegare?

Sai che cos'è una permutazione pari o dispari? Considera il cubo dimenticandoti dell'orientazione dei cubetti, ma tenendo conto della loro posizione.

I vertici sono 8 e vengono permutati tra loro. Gli spigoli sono 12 e vengono permutati tra loro. Quindi ogni posizione del cubo è data da una permutazione sui vertici e da una sugli spigoli.

La cosa che si scopre è che entrambe queste permutazioni devono avere la stessa parità. Questo è l'invariante. Quindi se pigli a piacere, che so, la permutazione dei vertici, resta individuata univocamente la parità della permutazione degli spigoli, quindi invece di avere tutte le permutazioni possibili (12!), hai solo quelle con la parità giusta, vale a dire esattamente la metà.

HINT per dimostrare l'invariante ha scritto:Un movimento elementare del cubo è ruotare una faccia di 1/4. Che cosa succede alle parità in quel caso?

fph ha scritto: I programmi più efficienti per la ricerca di soluzioni "corte" arrivano a circa una ventina di mosse nelle configurazioni più sfigate. Tempo fa ero arrivato a una pagina che ne parlava seguendo un paio di link, probabilmente con un abile uso di google riesci a ritrovarla.

Ritrovata: http://kociemba.org/cube.htm -- nella sezione "God's algorithm" parla dell'algoritmo ottimo per il cubo. Si sa che il numero che cerchi è compreso tra 20 e 30, e il creatore (con la c minuscola) della pagina ha scritto un algoritmo sorprendentemente buono, con un upper bound teorico di 30 mosse. Date un'occhiata anche al video del robot che risolve il cubo di rubik http://www.youtube.com/watch?v=jkft2qaKv_o e a questo

Di questo e altri problemi correlati si è già parlato QUI.

ma quindi questo significa che le permutazioni degli spigoli e degli angoli o sono entrambi pari o entrambi dispari?

Leggi l'altro thread e l'articolo che ho linkato, vedrai che trovi tutto quello che vuoi sapere, e anche di più. (cerchiamo di non avere 2 thread che parlano della stessa precisa identica cosa, vuoi?).

va bene scusa