Rubriks kube

[espen180]

En gitt konfigurasjon av rubriks kube (3x3x3) består av 9 ruter à 6 farger distribuert over 6 3x3 flater. For hver konfigurasjon er det gitt at midtrutene har forskjellige farger.

En løselig konfigurasjon er en som kan føres tilbake til konfigurasjonen der hver farge er isolert til én flate ved hjelp av tillatte trekk.

Et tillatt trekk er enhver rotasjon av en 3x3x1-del av kuben i planet til den aktuelle 3x3-flaten. Den midterste brikken i kuben er automatisk på riktig posisjon.

1) Vis at hvis en hjørnebrikke i en løselig konfigurasjon roteres én gang med klokka, og en vilkårlig annen hjørnebrikke roteres én gang mot klokka, er en resulterende konfigurasjonen løselig.

2) Vis at hvis to kantbrikker i en løselig konfigurasjon snus 180 grader, er den resulterende konfigurasjonen løselig.

3) Vis at hvis tre vilkårlige hjørnebrikker i en løselig konfigurasjon roteres én gang hver med klokka, er den resulterende konfigurasjonen løselig.

4) Gjelder 3) om brikkene roteres mot klokka?

[Karl_Erik]

Alle disse oppgavene kan løses ved ganske enkelt å finne en serie med trekk som (i den første oppgavens tilfelle) vrir ett hjørne med klokka og et vilkårlig annet hjørne mot klokka. For å løse den første, sett hjørnet du vil vri øverst til høyre på kubens forrerste flate og gjør RDR'D'RDR'D', roter så den øverste flaten til hjørnet du vil vri mot klokka står på samme plass, og gjør DRD'R'DRD'R', og vips har vi den konfigurasjonen beskrevet i oppgaven. Her betyr selvfølgelig R at man skal vri den høyre siden nitti grader med klokka, og D det tilsvarende for den nederste flaten. Vi ser også at dette kan brukes til å løse oppgave tre og fire på den opplagte måten.

Å løse den er så enkelt som å gjøre trekksekvensens invers. Den nødvendige trekksekvensen i oppgave to er noe lengre, så jeg orker ikke skrive den ned, men den er ikke så vanskelig å finne om man kan løse kuber. (Alternativt finnes det fullt av automatiske løsere på internett.)

[espen180]

5) Finnes det en løselig konfigurasjon som ikke kan løses på 27 trekk eller mindre?

[Karl_Erik]

Ikke i følge http://cubezzz.homelinux.org/drupal/?q=node/view/53. Finnes det et mer elementært bevis for dette?

[Dinithion]

Jeg mener det var ett firesiders bevis i New Scientist for noen måneder siden. Jeg leste det dog ikke. Jeg begynte, men skjønte fort at dette ikke var noe for meg.

[Charlatan]

Jeg mener det var ett firesiders bevis i -- Scientist for noen måneder siden. Jeg leste det dog ikke. Jeg begynte, men skjønte fort at dette ikke var noe for meg.

I så fall er et program som sjekker alle mulige kombinasjoner å foretrekke! Med mindre det krever for mye datakraft, og kan vel kanskje hende mtp hvor mange mulige permutasjoner som finnes.

[Dinithion]

Det står noe om ett bevis her:
http://arxivblog.com/?p=332

I følge det beviset kan alle kombinasjoner løses på 25 eller mindre trekk. Jeg løser ofte rubicscube når jeg kjeder meg eller ser på noe lett fordøyelig. Det virker helt usansynlig for meg at alle løsninger kan løses på mindre enn 26 trekk. Nå er jeg ikke veldig flink, så på 25 trekk har jeg kanskje fått til grunnflaten

Uansett, dette er bevist ved brute force, jeg mener artikkelen jeg leste var ett mer matematisk bevis. Om det er stor interesse, kan jeg se om jeg får tid å stikke innom biblioteket for å finne den igjen. Jeg tipper den er printet i perioden feb-juni 2010. (Hukommelse er ikke helt min greie )

[Gommle]

Det er bevist med bruteforce at alle 3x3-kuber kan løses med 20 eller færre trekk.

http://www.cube20.org/