Rubik's Cube Math

I 2010 beviste et internationalt team af forskere, at uanset hvor forvrænget en Rubiks terning blev, ville det ikke kræve mere end 20 træk at løse det. Deres beviser var dog afhængige af, hvad der svarer til 35 års tal knasende på en god moderne computer.

For terninger, der er større end standard Rubiks terning, kan en passende opsamling af startpositioner meget vel være ud over beregningskapaciteten for alle computere i verden. Men i september ledede Erik Demaine (til højre), en lektor i datalogi og teknik, et team inklusive sin far, CSAIL-gæsteprofessor Martin Demaine (til venstre), der demonstrerede det matematiske forhold mellem antallet af kvadrater i en terning og antal træk i den korteste løsning til dens mest krypterede tilstand.

Standardmåden at løse en Rubiks terning på er at finde en firkant, der er ude af position og flytte den på plads, mens resten af ​​terningen efterlades så lidt som muligt. Det giver en worst-case løsning, hvis antal træk er proportional med N2, hvor N er antallet af felter pr. række. Men holdet så, at under nogle omstændigheder kunne en enkelt sekvens af drejninger flytte flere firkanter på plads.

At beskrive disse omstændigheder matematisk var ingen let opgave. I den første time så vi, at det skulle være mindst N2/log N, fortæller Erik Demaine. Men så gik der mange måneder, før vi kunne bevise, at N2/log N var træk nok.

skjule